만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

소 세기

시간 제한1초메모리 제한1024 MB

요약
울타리 선분이 나눈 영역 가운데 소가 가장 많은 영역의 소 수를 구합니다. 울타리 바깥 영역도 후보에 포함합니다.
난이도

보통10점 중 6점

유형
기하, 그래프, 정렬
정답자
아직 제출이 없습니다

문제

팜 존(존 농부)의 농장에는 울타리로 둘러싸인 밭이 여러 개 있다. FJ는 지금 어느 밭에 소가 가장 많이 있는지 알고 싶어 한다. 농장은 2차원 평면이고, 소 NN마리(1≤N≤1001 \le N \le 100)가 정수 좌표에 흩어져 있다. 농장에는 KK개(1≤K≤10001 \le K \le 1000)의 울타리가 있다. 각 울타리는 길이가 0보다 큰 선분이며, 양 끝점은 정수 좌표다. 울타리끼리 교차하면 끝점에서만 만날 수 있다. 어떤 소도 울타리 위에 있지 않고, 다른 소와 같은 점에 있지도 않다.

밭은 울타리로 완전히 둘러싸인 영역이다. 소는 자신을 감싸는 가장 작은 넓이의 밭에 속한다. 어떤 밭에도 둘러싸이지 않은 소는 '마스터' 밭에 속한다. 소가 가장 많은 밭에 속한 소의 수를 구하라. 마스터 밭도 후보에 포함한다.

아래 세 그림에서 답은 (a) 2, (b) 2, (c) 1이다.

   +-------+               -------+                cow 1
   | cow 1 +--------+       cow 1 |               ________
   |          cow 2 |             |  cow 2       /       |
   +----------------+      -------+             +--------+

         (a)                  (b)                (c)      

입력

첫 줄에 두 정수 NN과 KK가 주어진다. 다음 NN줄에는 소의 xx 좌표와 yy 좌표가 한 줄에 하나씩 주어진다. 이어서 KK줄에는 울타리 두 끝점의 좌표 네 정수가 주어진다.

출력

소가 가장 많은 밭에 속한 소의 수를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    2 3
    4 5
    10 3
    3 0 7 0
    7 0 7 6
    0 6 7 6
    
    예상 출력
    2