파일 업로드

목장 울타리

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

우유 박람회에 다녀온 이후, 목축업자 태승이는 그의 목장 사이의 모든 N (1 <= N <= 500) 개의 울타리를 이동시켜 목장을 재설계하기로 했습니다! 각 울타리는 2D 평면에서 수평 또는 수직 선분으로 이루어져 있습니다. 두 울타리는 각 선분의 끝점에서만 만납니다.

태승이는 그의 목장에 C (1 <= C <= 500) 마리의 젖소를 가지고 있습니다. 각 젖소는 울타리에 없는 2D 평면의 한 점에 위치하고 있으며, 두 젖소가 같은 점에 위치하지 않습니다. 울타리에 닿지 않고 다른 젖소로 걸어갈 수 있다면 두 젖소는 같은 커뮤니티에 있다고 말합니다. 태승이가 가장 큰 커뮤니티의 크기를 결정하는 데 도움을 주십시오.

💻 입력
  • 줄 1: 두 개의 공백으로 구분된 정수, N과 C입니다.
  • 줄 2..1+N: 각 줄은 네 개의 정수: x1, y1, x2, y2를 포함합니다. 이것은 점 (x1, y1)에서 점 (x2, y2)까지 울타리를 설명합니다. 각 울타리는 수직 (x1 = x2) 또는 수평 (y1 = y2)입니다. 모든 좌표는 범위 0 .. 1,000,000 안에 있습니다.
  • 줄 2+N..1+N+C: 각 줄은 위치 (x, y)에서 젖소를 설명하는 두 정수 x와 y를 포함합니다. 모든 좌표는 범위 0 .. 1,000,000 안에 있습니다.
🖨️ 출력
  • 줄 1: 가장 큰 커뮤니티에 있는 젖소의 수입니다.

💻 예제 입력 1
7 3
0 0 10 0
10 0 10 5
12 5 10 5
10 5 1 5
12 5 12 7
0 7 12 7
0 7 0 0
3 4
6 6
17 3
🖨️ 예제 출력 1
2

출처: USACO 2012 December Contest, Bronze Problem 3. Crazy Fences