2차원 평면에서 두 선분이 만나는 경우의 수 > 문제은행



알고리즘 기하

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

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 10 회    시도횟수: 135 회   



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

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

72372583db04ef18d68a23068baf1147_1515410
 

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

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

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

72372583db04ef18d68a23068baf1147_1515410
 

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

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

 

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

72372583db04ef18d68a23068baf1147_1515412

 

 

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

(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


  기하알고리즘 PDF 


출처 : comkiwer



기하

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