comkiwer- 2차원 평면에서 두 선분이 만나는 경우의 수 > 문제은행 : 정보올림피아드&알고리즘



3122 : 2차원 평면에서 두 선분이 만나는 경우의 수

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
23 회   
시도횟수
107 회   

문제

2차원 평면에서 하나의 점은 x선분과 y선분을 이용하여 표현할 수 있다.

아래 그림과 같은 경우 점 a는 (1, 0), 점 b는 (4, 3) 이라고 나타낼 수 있다.

 

 

 

2차원 평면에서 선분은 두 개의 점으로 표현할 수 있다.

예를 들어 위 그림에서 점 a, b를 잇는 선분은 두 점의 좌표를 잇달아 적어 (1, 0, 4, 3)라고 나타낼 수 있다.

선분 ab는 아래 그림과 같다.

 

 

 

선분 정보가 N개 주어질때 임의의 두 선분이 서로 만나거나 교차하는 경우의 수를 구하는 프로그램을 작성하시오.

두 선분의 끝점이 닿기만하는 경우나 포개어 지는 경우도 경우의 수에 포함된다.

 

아래 예를 보면 5개의 선분이 주어진 경우이다.

 


 

 

 

두 선분이 서로 만나거나 교차하는 경우​를 순서쌍으로 나타내 보면

(2번 선분, 3번 선분), (2번 선분, 4번 선분), (2번 선분, 5번 선분) 

(3번 선분, 4번 선분), (3번 선분, 5번 선분)

(4번 선분, 5번 선분)

이렇게 6가지 경우가 있다.

 

 

 

 


입력형식

첫 행에 선분의 개수 N (1 <= N <= 10,000)이 주어진다.

두 번째 행부터 N행에 걸쳐 각 선분의 정보 sx, sy, ex, ey (-1,000,000 <= sx, sy, ex, ey <= 1,000,000)가 공백으로 구분되어 주어진다. 


출력형식

선분이 서로 만나거나 교차하는 모든 경우의 수를 구하여 출력한다.

입력 예

5
2 3 3 4
3 0 1 4
0 3 4 1
0 1 4 3
1 0 4 3

출력 예

6

Hint!



출처

comkiwer

기하

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP