정사각형자르기 > 문제은행



알고리즘 기하

1694 : 정사각형자르기

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



네 꼭짓점의 좌표가 각각 (10, 10), (10, -10), (-10, -10), (-10, 10)인 정사각형이 있다.

07f1ee470c4ca420b78cf86b19196679_1450335
 

양 끝점이 정사각형 밖에 위치한 선분들을 그려 정사각형을 여러 개의 영역으로 나눌 수 있다. 예를 들어 <그림 2>와 같이 세 개의 선분을 그리면 정사각형은 일곱 개의 영역으로 나누어진다.

07f1ee470c4ca420b78cf86b19196679_1450335

셋 이상의 선분은 한 점 위에서 만나지 않으며 두 선분은 같은 직선상에 있지 않다.

 

선분의 개수 N과 선분의 양 끝점의 좌표가 주어질 때 정사각형이 이들 선분들에 의해 몇 개의 영역으로 나누어지는지를 출력하는 프로그램을 작성하시오.


첫째 줄에 선분의 개수 N이 주어진다. 둘째 줄부터 한 줄에 하나씩 선분의 양 끝점의 좌표를 나타내는 네 개의 정수 x1, y1, x2, y2가 주어진다. 이는 (x1, y1)와 (x2, y2)를 잇는 선분을 의미한다. 

N은 100 이하의 자연수이고, x1, y1, x2, y2는 모두 -1000 이상 1000 이하의 정수이다. 모든 선분의 양 끝점은 정사각형 밖에 위치한다.


첫째 줄에 입력으로 주어진 선분들에 의해 정사각형이 몇 개의 영역으로 나누어지는지 출력한다.

3 
-15 5 15 5 
12 12 -14 -14 
-7 18 0 -15
7


두 수의 정밀도는 소수이하 6자리까지만 비교합니다.
다시 말해 두수가 소수이하 6자리까지 같다면 같은 수로 봅니다.






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.