복잡하게 얽힌 울타리

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

요약
울타리들이 서로 겹치지 않는 닫힌 다각형을 이루며, 울타리를 넘지 않고 서로 이동할 수 있는 소들의 최대 무리 크기를 구한다.
난이도

어려움10점 중 8점

유형
기하, 그래프, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

농부 John이 목장 사이의 울타리 NN개를 모두 새로 배치하려고 한다 (1≤N≤10001 \le N \le 1000). 각 울타리는 2차원 평면 위의 선분이다. 두 울타리는 오직 끝점에서만 만날 수 있으며, 모든 울타리는 자신의 두 끝점에서 각각 정확히 하나씩, 총 두 개의 다른 울타리와 만난다. 따라서 울타리들은 서로 겹치지 않는 하나 이상의 닫힌 다각형을 이룬다.

농부 John에게는 소 CC마리가 있다 (1≤C≤10001 \le C \le 1000). 각 소는 어떤 울타리 위에도 놓이지 않은 한 점에 서 있으며, 두 소가 같은 점에 있는 경우는 없다. 어떤 소가 울타리를 하나도 넘지 않고 다른 소가 있는 곳까지 걸어갈 수 있으면, 두 소는 같은 무리(community) 에 속한다.

가장 큰 무리에 속한 소의 수를 구하여라.

입력

  • 첫째 줄: 두 정수 NN과 CC가 공백으로 구분되어 주어진다.
  • 다음 NN개의 줄: 각 줄에 정수 네 개 x1 y1 x2 y2x_1\ y_1\ x_2\ y_2가 주어지며, (x1,y1)(x_1, y_1)에서 (x2,y2)(x_2, y_2)까지 이어지는 울타리를 뜻한다.
  • 그다음 CC개의 줄: 각 줄에 정수 두 개 x yx\ y가 주어지며, 소 한 마리의 위치를 뜻한다.

모든 좌표는 0 이상 1,000,000 이하의 정수이다.

출력

  • 가장 큰 무리에 속한 소의 수를 한 줄에 출력한다.

힌트

울타리들이 닫힌 고리를 이루므로, 두 소는 자신들을 감싸는 고리의 집합이 완전히 같을 때에만 같은 무리에 속한다. 예제에서 울타리들은 하나의 정사각형과 그 안의 삼각형 두 개를 이루며, 네 마리 중 두 마리는 같은 고리 집합 안에 있어 같은 무리를 이루고 나머지 두 마리는 각자 혼자다.

예제3

  1. 예제 1

    입력
    10 4
    0 0 10 0
    10 0 10 10
    0 0 0 10
    10 10 0 10
    8 8 9 8
    9 8 8 9
    8 9 8 8
    2 7 3 2
    3 2 7 5
    7 5 2 7
    15 3
    1 4
    4 5
    7 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    4 5
    0 0 10 0
    10 0 10 10
    10 10 0 10
    0 10 0 0
    5 5
    2 2
    8 8
    15 15
    15 5
    
    예상 출력
    3
    
  3. 예제 3

    입력
    3 5
    0 0 10 0
    10 0 5 10
    5 10 0 0
    5 3
    5 5
    4 4
    0 8
    9 8
    
    예상 출력
    3