Informatica Online Judge

  다이어트 [0671 / 029F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 27   Total Tried : 29


The Champion of this Problem (C++) : gs15067 - 0ms / 1482byte
My Best Submission (C++) : N/A

[]

Background

좌표평면 상에 N채의 집들이 있고, 집마다 서로 다른 1 이상 N 이하의 번지수가 있습니다.

tncks0121은 심심하기 때문에 집들을 돌아다니는 여행을 하기로 했습니다.

집들 사이에는 두 집을 선분으로 연결하는 도로가 M개 있는데,
그는 고귀하기 때문에 집들을 돌아다닐 때 도로만을 이용합니다.
두 집을 선분으로 연결하는 도로의 거리는 두 집의 좌표를 잇는 선분의 길이와 같습니다.

그는 길치이기 때문에 길을 잃지 않기 위해서 초기에 아무 집이나 고른 후,
현재 있는 집과 도로로 연결되어 있는 집들 중, x좌표와 y좌표의 크기가
현재 있는 집보다 둘 모두 큰 집으로만 계속 가려고 합니다.

tncks0121은 심심하기 때문에 집들을 최대한 많이 들르고 싶습니다.

또한 그는 다이어트 중이기 때문에, 들를 수 있는 집 수가 같다면
처음에 집을 고른 후부터 여행을 마칠 때 까지 간 거리를 최대로 하고 싶어합니다.

그의 다이어트를 도와줍시다.

Input

첫 번째 줄에 집의 수 N(N은 100,000이하의 자연수)와 도로의 수 M(M은 100,000이하의 자연수)이 주어집니다.
다음 N개의 줄에는 i+1번째 줄에 i번째 집의 좌표(xi,yi)가 주어집니다.
(단, 주어지는 모든 좌표의 x좌표와 y좌표는 0이상 100,000,000이하의 정수)

그 다음 M개의 줄에 도로로 연결된 두 집의 번지수의 순서쌍 (a1, b1), (a2, b2), ..., (am, bm)이 차례대로 주어집니다.

Output

tnck가 여행을 마칠 때까지 들를 수 있는 최대 집의 수를 첫째 줄에 출력하고, 둘째 줄에 그때 갈 수 있는 거리의 최댓값을 소수점 뒤 여섯 번째 자리까지 출력합니다.

IO Example

입력
5 3
0 0
1 3
4 5
7 8
10 11
1 3
2 4
4 5

출력
3
12.052890

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]