반직선이 만나는 경우의 수 > 문제은행



알고리즘 기하

3262 : 반직선이 만나는 경우의 수

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 11 회    시도횟수: 49 회   



N개의 반직선이 2차원 평면에 주어진다.

반직선의 시작점은 0초과 L미만의 정수값을 갖는다.

N개의 반직선중에 임의의 두 반직선이 만나는 경우의 수를 구하라.

 

N개의 반직선의 시작점은 모두 다르다.

각 반직선은 시작점과 움직이는 방향점으로 표현된다.

두 반직선이 만나는 경우 만나는 점이(0, 0) ~ (L, L)에 위치한 경우만 유효한 것으로 간주한다. 

오차의 범위는 소수이하 6자리까지이다.

 

입력예에 대한 그림설명은 아래와 같다.

 

335aa020a8d785055a8aac61f9b9be6e_1540261
 




첫 행에 반직선의 개수 N(1 <= N <= 1,000)과 평면의 크기 L(10 <= L <= 10,000)이 공백으로 구분되어 주어진다.
다음 N행에 걸쳐 각 반직선의 정보가 주어진다.
반직선의 정보는 시작점과 방향을 나타내는 4개의 정수
sx, sy, dx, dy ( 0 < sx, sy, dx, dy < L ) 가 주어진다.
이는 점(sx, sy)로부터 점(dx, dy)로 향한 반직선을 의미한다.



N개의 반직선중에 임의의 두 반직선이 (0, 0) ~ (L, L) 범위에서 만나는 경우의 수를 출력한다.


10 20
2 13 9 15
6 10 5 11
7 12 6 11
13 14 11 12
8 1 6 2
6 4 10 5
9 8 11 8
10 4 4 10
15 19 15 1
8 17 10 15
15


  기하알고리즘 PDF 


출처 : comkiwer



geometry, 기하

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.