파일 업로드

🎨AI 리소스 생성

프롬프트 없음

목장 울타리2

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

우유 박람회에 다녀온 이후, 농부 태승이는 그의 목장 사이의 모든 N (1 <= N <= 1000) 개의 울타리를 이동하여 목장을 재설계하기로 했습니다! 각 울타리는 2D 평면에서 선분으로 설명됩니다. 두 울타리는 각 선분의 끝점에서만 만납니다. 각 울타리는 정확히 둘 다 끝점에서 다른 울타리 두 개에 닿습니다.

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

 

💻 입력
  • 1번째 줄: 두 개의 공백으로 구분된 정수 N과 C.
  • 2번째 줄..1+N번째 줄: 각 라인은 네 개의 정수: x1, y1, x2, y2를 포함하며, 이는 점 (x1,y1)에서 점 (x2,y2)까지 울타리를 나타냅니다. 모든 좌표는 0..1,000,000 범위의 정수입니다.
  • 2+N번째 줄..1+N+C번째 줄: 각 줄은 젖소의 위치를 설명하는 두 개의 정수 x와 y를 포함합니다. 모든 좌표는 0..1,000,000 범위의 정수입니다.
🖨️ 출력
  • 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
🖨️ 예제 출력 1
2

출처: USACO 2012 December Contest, Silver Problem 1. Crazy Fences