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

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

패스트푸드

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

요약
한 변이 10km인 정사각형 도시 안의 후보 지점 최대 50개에 대해, 각 지점의 보로노이 영역이 도시에서 차지하는 넓이를 구하고 반올림한 백분율로 출력한다.
난이도

어려움10점 중 9점

유형
기하, 분할 정복, 구현, 수학
정답자
아직 제출이 없습니다

문제

새로운 Veggie Vittles 패스트푸드 체인점 후보지 NN곳이 주어집니다. 도시는 한 변의 길이가 1010km인 정사각형이며, 인구는 도시 전역에 균일한 밀도로 분포합니다.

도시의 각 지점은 자신에게 가장 가까운 매장 하나가 담당합니다. 각 매장에 대해, 그 매장이 '가장 가까운 매장'이 되는 영역이 도시 전체 인구에서 차지하는 비율(퍼센트)을 구하세요. 인구 밀도가 균일하므로, 이 비율은 그 매장이 가장 가까운 영역의 넓이가 도시 전체 넓이에서 차지하는 비율과 같습니다.

입력

입력은 여러 개의 테스트 케이스로 이루어질 수 있습니다. 각 테스트 케이스의 첫 줄에는 열려는 매장의 수 NN (1≤N≤50)(1 \le N \le 50)이 주어집니다. 이어지는 NN개의 줄에는 각 매장의 좌표 xx, yy가 주어지며, 각 좌표는 00 이상 1010 이하의 정수입니다. NN이 00인 줄이 입력의 끝을 나타냅니다.

출력

각 테스트 케이스에 대해, 입력에 주어진 순서대로 매장마다 한 줄씩 출력합니다. 각 줄은 다음 형식을 정확히 따릅니다.

Restaurant at (x,y) serves P% of the population.

여기서 (x,y)(x,y)는 매장의 좌표이고, PP는 그 매장이 가장 가까운 매장이 되는 영역이 차지하는 인구 비율을 퍼센트로 나타낸 값을 가장 가까운 정수로 반올림한 것입니다(소수 부분이 정확히 0.50.5이면 올림). 서로 다른 테스트 케이스의 출력은 빈 줄 없이 이어서 출력합니다.

예제5

  1. 예제 1

    입력
    3
3 5
5 7
7 5
0
    예상 출력
    Restaurant at (3,5) serves 38% of the population.
Restaurant at (5,7) serves 25% of the population.
Restaurant at (7,5) serves 38% of the population.

  2. 예제 2

    입력
    1
5 5
0
    예상 출력
    Restaurant at (5,5) serves 100% of the population.

  3. 예제 3

    입력
    2
0 0
10 10
0
    예상 출력
    Restaurant at (0,0) serves 50% of the population.
Restaurant at (10,10) serves 50% of the population.

  4. 예제 4

    입력
    3
0 5
5 5
10 5
0
    예상 출력
    Restaurant at (0,5) serves 25% of the population.
Restaurant at (5,5) serves 50% of the population.
Restaurant at (10,5) serves 25% of the population.

  5. 예제 5

    입력
    4
0 0
0 10
10 0
10 10
0
    예상 출력
    Restaurant at (0,0) serves 25% of the population.
Restaurant at (0,10) serves 25% of the population.
Restaurant at (10,0) serves 25% of the population.
Restaurant at (10,10) serves 25% of the population.