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

문제

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

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

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

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

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

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

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

입력

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

각 테스트 케이스의 첫 줄엔 너겟의 수 N(1 ≤ N ≤ 200)이 주어진다.

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

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

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

피자의 반지름은 1이다.

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

출력

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

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

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

예제 입력 1

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

예제 출력 1

Data Set 1: 1 slices

Data Set 2: 2 slices

힌트

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

W3sicHJvYmxlbV9pZCI6IjUxODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWM3OTAhIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYjBcdWFjZmMgXHViYzFjXHVkNDVjXHViM2M0IFx1YjA1ZFx1YjBhY1x1YWNlMCwgXHVjNzc0XHVjODFjIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjOTExXHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc3OCBcdWQ1M2NcdWM3OTBcdWI5N2MgXHViYTM5XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWQ1M2NcdWM3OTBcdWFjMDAgXHVjNzc0XHVjMGMxXHVkNTU4XHVhYzhjIFx1YzBkZFx1YWUzNCBcdWQwZDNcdWM1ZDAgXHViNjEwIFx1Y2Y1NFx1YjUyOVx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1M2NcdWM3OTAgXHVjNzA0XHVjNWQ0IFx1YjEwOFx1YWM5Zlx1Yzc3NCBcdWJhODcgXHVhYzFjIFx1YzYyY1x1Yjc3Y1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDUzY1x1Yzc5MFx1YjI5NCBcdWM2ZDBcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWM3OTBcdWI5N2MgXHViNTRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWMxMzggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVkNTNjXHVjNzkwXHViMjk0IFx1ZDUzY1x1Yzc5MFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDQgXHViNTMwXHViNzdjXHVjMTFjXHViOWNjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxMDhcdWFjOWZcdWM3NDQgXHVjNzkwXHViOTc0XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWM4MDhcdWIzMDBcdWI4NWMgXHVjNzg4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQ8XC9saT5cclxuXHQ8bGk+XHVkNTNjXHVjNzkwXHVhYzAwIFx1YjJlNCBcdWM3OThcdWI5YjAgXHViNGE0IFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWJhYThcdWI0ZTAgXHVjODcwXHVhYzAxXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWIzZDlcdWM3N2NcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWFjMDEgXHVjODcwXHVhYzAxXHVjNWQwIFx1YjE5M1x1Yzc3OCBcdWIxMDhcdWFjOWZcdWM3NTggXHVjMjE4IFx1YjYxMFx1ZDU1YyBcdWIzZDlcdWM3N2NcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjMwMFx1ZDY4Y1x1YjNjNCBcdWIwNWRcdWIwYWNcdWIyOTRcdWIzNzAgXHVhY2UwXHVjNzkxIFx1YjEwOFx1YWM5ZiBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMmY4XHVjNmMwXHVjNzc0IFx1YjA5OFx1YWM4YyBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1YjMwMFx1ZDY4YyBcdWNjMzhcdWFjMDBcdWM3OTBcdWFjMDAgXHViOWNlXHViMmU0XHViY2Y0XHViMmM4IFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWQ1M2NcdWM3OTBcdWI5N2MgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWM3OTBcdWI5NzRcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWJlNjhcdWI5YWMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlYyBcdWQ1M2NcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1Yzc5OFx1Yjc3Y1x1YmNmNFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWM1NDggXHVjNzkwXHViOTdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDAsIFx1ZDUzY1x1Yzc5MFx1YjI5NCBcdWNkMWQgMVx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1YjEwOFx1YWM5Zlx1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjQgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViMTA4XHVhYzlmXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCAmYWxwaGE7IHIgXHVjNzU4IFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZhbHBoYTtcdWIyOTQgMCAmbGU7ICZhbHBoYTsgJmx0OyAyJnBpOyBcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViYTcwLCBcdWQ1M2NcdWM3OTBcdWM3NTggXHVjOTExXHVjMmVjXHVjNWQwXHVjMTFjIFx1YmMxOFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3YjAgXHVhYzAxXHViM2M0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5yXHVjNzQwIDAgJmx0OyByICZsZTsgMSBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTcwLCBcdWQ1M2NcdWM3OTBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YjEwOFx1YWM5Zlx1Yzc3NCBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1M2NcdWM3OTBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQwIDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjEwOFx1YWM5Zlx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNzkxXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTc0XHViM2M0IFx1YmIzNFx1YmMyOVx1ZDU1OFx1YmE3MCwgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWIxMDhcdWFjOWZcdWIzYzQgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IERhdGEgU2V0IEs6IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0LDxcL3A+XHJcblxyXG48cD5cdWQ1M2NcdWM3OTBcdWI5N2MgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0Y1x1Yzc1OCBcdWM4NzBcdWFjMDEgXHVjMjE4IHNcdWM1ZDAgXHViMzAwXHVkNTc0ICZxdW90O3Mgc2xpY2VzJnF1b3Q7IChcdWI1MzBcdWM2MzRcdWQ0NWMgXHVjODFjXHVjNjc4KVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkNCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc1OCBcdWJiMzhcdWJjOTVcdWM4MDEgXHVjNjI0XHViOTU4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzEyMCBcdWMyZTBcdWFjYmRcdWM0ZjBcdWM5YzAgXHViOWQwXHVjNzkwLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTE4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpenphISIsImRlc2NyaXB0aW9uIjoiPHA+RmluYWxseSwgd2UgZ2V0IHRvIHRoZSBtb3N0IGltcG9ydGFudCBwYXJ0IG9mIHRoZSBjb250ZXN0OiBFYXRpbmcgdGhlIHBpenphLiBCdXQgZXZlbiBoZXJlLCBwcm9ibGVtcyBhcmUgbHVya2luZyEgVGhlIHBpenphIGhhcyBkZWxpY2lvdXMgc295IG51Z2dldHMgb24gaXQsIGJ1dCBpdCBpc24mcnNxdW87dCBjdXQgeWV0LiBTbyB3ZSBoYXZlIHRvIGN1dCBpdCBpbnRvIHNsaWNlcy4gVGhlcmUgYXJlIHR3byBpbXBvcnRhbnQgY29uc3RyYWludHMgd2UgaGF2ZSB0byBtZWV0OiBldmVyeSBzbGljZSBtdXN0IGhhdmUgdGhlIHNhbWUgc2l6ZSwgYW5kIGV2ZXJ5IHNsaWNlIG11c3QgaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2Ygc295IG51Z2dldHMgb24gaXQuIFRvIG1ha2UgdGhpbmdzIHdvcnNlLCB0aGUgcGl6emEgaXMgY2lyY3VsYXIsIGFuZCB3ZSBjYW4gb25seSBjdXQgYWxvbmcgYSBzdHJhaWdodCBsaW5lIGZyb20gdGhlIGNlbnRlciBvZiB0aGUgY2lyY2xlIHRvIGl0cyBjaXJjdW1mZXJlbmNlLiBBbmQgd2UgY2FuIG5ldmVyIGN1dCB0aHJvdWdoIGEgc295IG51Z2dldCwgaXQgbXVzdCBhbHdheXMgYmUgb24gb25lIHNpZGUgb2YgdGhlIGN1dCBvciB0aGUgb3RoZXIuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBwb3NpdGlvbnMgb2YgdGhlIHNveSBudWdnZXRzLCBkZXRlcm1pbmVzIHdoaWNoIGlzIHRoZSBsYXJnZXN0IG51bWJlciBvZiBzbGljZXMgaW50byB3aGljaCB0aGUgcGl6emEgY2FuIGJlIGN1dCBzdWNoIHRoYXQgZXZlcnkgcGllY2UgaGFzIHRoZSBzYW1lIHNpemUgYW5kIHRoZSBzYW1lIG51bWJlciBvZiBzb3kgbnVnZ2V0cyAobm90aWNlIHRoYXQgYSBwaXp6YSBjYW4gYWx3YXlzIGJlIGN1dCBpbnRvIDEgc2xpY2UgJm1kYXNoOyBzbyB0aGVyZSBhbHdheXMgaXMgYSBzb2x1dGlvbi4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBpcyB0aGUgbnVtYmVyIEsgb2YgaW5wdXQgZGF0YSBzZXRzLCBmb2xsb3dlZCBieSBLIGRhdGEgc2V0cywgZWFjaCBvZiB0aGUgZm9sbG93aW5nIGZvcm06PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgTiBvZiBzb3kgbnVnZ2V0cyBvbiB0aGUgcGl6emEgKDEgJmxlOyBOICZsZTsgMjAwKS4gVGhpcyBpcyBmb2xsb3dlZCBieSBOIGxpbmVzLCBkZXNjcmliaW5nIHRoZSBwb3NpdGlvbnMgb2YgdGhlIHNveSBudWdnZXRzLiBFYWNoIHBvc2l0aW9uIGlzIGdpdmVuIGluIHBvbGFyIGNvb3JkaW5hdGVzLCBtZWFzdXJlZCBmcm9tIHRoZSBjZW50ZXIgb2YgdGhlIHBpenphLiBUaGF0IGlzLCBhIHBvc2l0aW9uIGlzIGEgcGFpciAmbGRxdW87JmFscGhhOyByJnJkcXVvOywgd2hlcmUgMCAmbGU7ICZhbHBoYTsgJmx0OyAyJnBpOyBpcyB0aGUgY291bnRlcmNsb2Nrd2lzZSBhbmdsZSBiZXR3ZWVuIHRoZSBwb3NpdGl2ZSB4LWF4aXMgYW5kIHRoZSBsaW5lIGZyb20gdGhlIHBpenphIGNlbnRlciB0byB0aGUgc295IG51Z2dldC4gMCAmbHQ7IHIgJmxlOyAxIGlzIHRoZSBkaXN0YW5jZSBvZiB0aGUgbnVnZ2V0IGZyb20gdGhlIGNlbnRlciAoZWFjaCBwaXp6YSB3aWxsIGhhdmUgcmFkaXVzIDEpLiBXZSBhc3N1bWUgdGhhdCBudWdnZXRzIGFyZSBwb2ludHMsIGFuZCBubyB0d28gbnVnZ2V0cyB3aWxsIGJlIGx5aW5nIG9uIHRoZSBzYW1lIHNwb3Qgb2YgdGhlIHBpenphLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBvdXRwdXQgaXRzIG51bWJlciwgZm9sbG93ZWQgYnkgdGhlIG1heGltdW0gbnVtYmVyIG9mIHNsaWNlcyBpbnRvIHdoaWNoIGl0IGNhbiBiZSBjdXQgYWNjb3JkaW5nIHRvIHRoZSBhYm92ZSBydWxlcy4gUmVtZW1iZXIgdGhhdCBubyBjdXQgY2FuIGdvIHRocm91Z2ggYSBzb3kgbnVnZ2V0LiBPdXRwdXQgZm9yIGRpZmZlcmVudCBkYXRhIHNldHMgc2hvdWxkIGJlIHNlcGFyYXRlZCBieSBhbiBlbXB0eSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Eb24mcnNxdW87dCB3b3JyeSBhYm91dCB0aGUgZ3JhbW1hciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

University > The USC Programming Contest > Fall 2007 F번