소 세기
시간 제한1초메모리 제한1024 MB
울타리 선분이 나눈 영역 가운데 소가 가장 많은 영역의 소 수를 구합니다. 울타리 바깥 영역도 후보에 포함합니다.
문제
팜 존(존 농부)의 농장에는 울타리로 둘러싸인 밭이 여러 개 있다. FJ는 지금 어느 밭에 소가 가장 많이 있는지 알고 싶어 한다. 농장은 2차원 평면이고, 소 마리()가 정수 좌표에 흩어져 있다. 농장에는 개()의 울타리가 있다. 각 울타리는 길이가 0보다 큰 선분이며, 양 끝점은 정수 좌표다. 울타리끼리 교차하면 끝점에서만 만날 수 있다. 어떤 소도 울타리 위에 있지 않고, 다른 소와 같은 점에 있지도 않다.
밭은 울타리로 완전히 둘러싸인 영역이다. 소는 자신을 감싸는 가장 작은 넓이의 밭에 속한다. 어떤 밭에도 둘러싸이지 않은 소는 '마스터' 밭에 속한다. 소가 가장 많은 밭에 속한 소의 수를 구하라. 마스터 밭도 후보에 포함한다.
아래 세 그림에서 답은 (a) 2, (b) 2, (c) 1이다.
+-------+ -------+ cow 1
| cow 1 +--------+ cow 1 | ________
| cow 2 | | cow 2 / |
+----------------+ -------+ +--------+
(a) (b) (c)
입력
첫 줄에 두 정수 과 가 주어진다. 다음 줄에는 소의 좌표와 좌표가 한 줄에 하나씩 주어진다. 이어서 줄에는 울타리 두 끝점의 좌표 네 정수가 주어진다.
출력
소가 가장 많은 밭에 속한 소의 수를 한 줄에 출력한다.