시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

결과 발표도 끝났고, 이제 대회에서 가장 중요한 시간인 피자를 먹는 시간이 되었다.

하지만 피자가 이상하게 생긴 탓에 또 코딩을 해야 한다.

피자 위엔 너겟이 몇 개 올라가 있으며, 피자는 원형이다.

피자를 자를 때는 다음의 세 조건을 만족해야 한다.

  • 피자는 피자의 반지름을 따라서만 자를 수 있다.
  • 너겟을 자르는 일은 절대로 있어서는 안 된다
  • 피자가 다 잘린 뒤 만들어진 모든 조각의 크기는 동일해야 하며, 각 조각에 놓인 너겟의 수 또한 동일해야 한다.

대회도 끝났는데 고작 너겟 때문에 싸움이 나게 생겼다. 대회 참가자가 많다보니 당신은 피자를 가능한 한 최대한 많은 조각으로 자르고 싶다. 빨리 프로그램을 작성하여 피자를 적절히 잘라보도록 하자.

피자를 안 자를 수도 있다. 이 경우에, 피자는 총 1조각이 된다.

입력

첫 줄에 테스트 케이스의 수 K가 주어진다.

각 테스트 케이스의 첫 줄엔 너겟의 수 N이 주어진다.

이어 N줄에 걸쳐 너겟의 위치가 α r 의 형식으로 주어진다.

α는 0 ≤ α < 2π 를 만족하며, 피자의 중심에서 반시계방향으로 잰 각도이다.

r은 0 < r ≤ 1 을 만족하며, 피자의 중심으로부터 너겟이 떨어진 거리이다.

피자의 반지름은 1이다.

너겟은 매우 작은 하나의 점으로 생각해도 무방하며, 어떤 두 너겟도 같은 위치에 존재하지 않는다.

출력

각 테스트 케이스마다 Data Set K: 를 출력한 뒤,

피자를 가장 많은 조각으로 나누었을 때의 조각 수 s에 대해 "s slices" (따옴표 제외)를 출력한다.

각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.

예제 입력

2
2
1.57 0.5
1.57 0.7
4
0.7 0.9
1.5 0.1
1.8 0.5
3.05 1.0

예제 출력

Data Set 1: 1 slices

Data Set 2: 2 slices

힌트

출력의 문법적 오류에 대해선 신경쓰지 말자.

출처

University > The USC Programming Contest > Fall 2007 F번