다각형의 개수
시간 제한2초메모리 제한128 MB
최대 50개의 직선이 만드는 평면 분할에서 유한한 다각형 영역의 개수를 구하는 문제입니다.
문제
매우 큰 종이를 XY 좌표평면이라고 생각하자. 다솜이는 이 평면에 직선 N개를 그었다. 입력의 각 줄에는 서로 다른 두 점이 주어지며, 그 두 점을 지나는 무한한 직선을 그린 것으로 본다.
그려진 직선들은 평면을 여러 영역으로 나눈다. 직선 배열에서 생기는 유계 영역은 모두 볼록 다각형이고, 그 내부를 다른 직선이 지나지 않는다. 각 직선을 정하는 두 점의 좌표가 주어졌을 때, 이러한 다각형 영역이 모두 몇 개인지 구하라.
입력
첫째 줄에 직선의 개수 N이 주어진다. N은 50 이하의 자연수이다.
둘째 줄부터 N개의 줄에는 한 직선 위의 서로 다른 두 점의 좌표 x1, y1, x2, y2가 이 순서로 주어진다. 모든 좌표는 -10,000 이상 10,000 이하의 정수이다. 입력 줄의 정보가 완전히 중복되는 경우는 없다.
출력
첫째 줄에 다각형 영역의 개수를 출력한다.