복잡한 울타리

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

한 농부가 목초지 사이에 $N$ ($1 \le N \le 500$)개의 울타리를 새로 놓아 농장을 재설계한다. 각 울타리는 2차원 평면 위의 수평 또는 수직 선분이다. 두 울타리가 만난다면 오직 양 끝점에서만 만난다.

농장에는 $C$ ($1 \le C \le 500$)마리의 소가 있다. 각 소는 어떤 울타리 위에도 놓여 있지 않은 점에 서 있으며, 두 소가 같은 점에 있지는 않다. 한 소에서 다른 소로 울타리를 전혀 건드리지 않고 걸어갈 수 있으면 두 소는 같은 공동체에 속한다고 한다. 가장 큰 공동체의 크기를 구하여라.

입력

  • 첫째 줄: 공백으로 구분된 두 정수 $N$과 $C$.
  • 둘째 줄부터 $N+1$번째 줄까지: 각 줄에 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어지며, 이는 점 $(x_1, y_1)$에서 점 $(x_2, y_2)$까지 이어지는 울타리를 나타낸다. 각 울타리는 수직($x_1 = x_2$)이거나 수평($y_1 = y_2$)이다. 모든 좌표는 $0$ 이상 $1{,}000{,}000$ 이하이다.
  • $N+2$번째 줄부터 $N+1+C$번째 줄까지: 각 줄에 두 정수 $x$와 $y$가 주어지며, 이는 소의 위치를 나타낸다. 모든 좌표는 $0$ 이상 $1{,}000{,}000$ 이하이다.

출력

  • 첫째 줄: 가장 큰 공동체에 속한 소의 수.

힌트

두 소가 같은 공동체에 속하는 것은, 두 소의 위치를 잇는 연속적인 경로가 울타리를 전혀 건드리지 않고 존재할 때와 정확히 같다. 울타리는 끝점에서만 서로 만나므로, 한쪽 끝이 다른 울타리에 닿지 않고 열려 있는 울타리는 영역을 완전히 막지 못한다. 소는 그런 열린 끝을 돌아서 지나갈 수 있다. 오직 함께 어떤 영역을 완전히 둘러싸는 울타리들만이 서로 다른 공동체를 나눈다.