아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

복잡한 울타리

면접 대비

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

요약
끝점에서만 만나는 가로 및 세로 울타리와 소들의 위치가 주어질 때, 울타리에 닿지 않고 서로 이동할 수 있는 소들의 최대 무리 크기를 구한다.
난이도

보통10점 중 6점

유형
기하, 그래프, 유니온 파인드, BFS
정답자
아직 제출이 없습니다

문제

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

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

입력

  • 첫째 줄: 공백으로 구분된 두 정수 NN과 CC.
  • 둘째 줄부터 N+1N+1번째 줄까지: 각 줄에 네 정수 x1x_1, y1y_1, x2x_2, y2y_2가 주어지며, 이는 점 (x1,y1)(x_1, y_1)에서 점 (x2,y2)(x_2, y_2)까지 이어지는 울타리를 나타낸다. 각 울타리는 수직(x1=x2x_1 = x_2)이거나 수평(y1=y2y_1 = y_2)이다. 모든 좌표는 00 이상 1,000,0001{,}000{,}000 이하이다.
  • N+2N+2번째 줄부터 N+1+CN+1+C번째 줄까지: 각 줄에 두 정수 xx와 yy가 주어지며, 이는 소의 위치를 나타낸다. 모든 좌표는 00 이상 1,000,0001{,}000{,}000 이하이다.

출력

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

힌트

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

예제1

  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
    
    예상 출력
    2