레이팅 미적용\(1 \ldots N\)으로 편리하게 번호가 붙은 농부 존의 \(N\)마리 소들 (\(2 \leq N \leq 10^5\))은 "음메 네트워크"를 중심으로 하는 복잡한 사회 구조를 가지고 있다. 음메 네트워크란 자기 그룹 안에서는 소통하지만 다른 그룹과는 소통하지 않는 소들의 소그룹이다.
각 소는 농장의 2차원 지도 위에서 서로 다른 \((x,y)\) 위치에 있으며, \(M\)쌍의 소들이 (\(1 \leq M < 10^5\)) 서로 음메 하고 운다는 것을 알고 있다. 서로 음메 하는 두 소는 같은 음메 네트워크에 속한다.
농장을 정비하기 위해, 농부 존은 변이 \(x\)축과 \(y\)축에 평행한 직사각형 울타리를 짓고자 한다. 농부 존은 적어도 하나의 음메 네트워크가 울타리 안에 완전히 포함되도록 하고 싶다(직사각형 경계 위의 소도 포함된 것으로 친다). 이 요구를 만족하는 울타리의 가능한 최소 둘레를 구하는 것을 도와주자. 이 울타리는 너비나 높이가 0이어도 된다.
문제 제공: Brian Dean
문제 제공: Brian Dean
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(N\)개의 줄 각각에는 소 한 마리의 \(x\), \(y\) 좌표 (최대 \(10^8\)인 음이 아닌 정수)가 주어진다. 다음 \(M\)개의 줄 각각에는 소 \(a\)와 \(b\) 사이의 음메 연결을 나타내는 두 정수 \(a\)와 \(b\)가 주어진다. 모든 소는 적어도 하나의 음메 연결을 가지며, 같은 연결이 입력에 중복해서 주어지지 않는다.
농부 존의 요구를 만족하는 울타리의 최소 둘레를 출력한다.
fenceplan.in · 출력을 쓸 파일 fenceplan.out7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 610riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > US Open > Silver