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

문제

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

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

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

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

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

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

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

입력

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

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

이어 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+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1YjEwOFx1YWM5Zlx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNCBOXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIxMDhcdWFjOWZcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwICZhbHBoYTsgciBcdWM3NTggXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JmFscGhhO1x1YjI5NCAwICZsZTsgJmFscGhhOyAmbHQ7IDImcGk7IFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzAsIFx1ZDUzY1x1Yzc5MFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM1ZDBcdWMxMWMgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzdiMCBcdWFjMDFcdWIzYzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPnJcdWM3NDAgMCAmbHQ7IHIgJmxlOyAxIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzAsIFx1ZDUzY1x1Yzc5MFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHViMTA4XHVhYzlmXHVjNzc0IFx1YjVhOFx1YzViNFx1YzljNCBcdWFjNzBcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDAgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTA4XHVhYzlmXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM3OTFcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWIzYzQgXHViYjM0XHViYzI5XHVkNTU4XHViYTcwLCBcdWM1YjRcdWI1YTQgXHViNDUwIFx1YjEwOFx1YWM5Zlx1YjNjNCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgRGF0YSBTZXQgSzogXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWI0YTQsPFwvcD5cclxuXHJcbjxwPlx1ZDUzY1x1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHViNTRjXHVjNzU4IFx1Yzg3MFx1YWMwMSBcdWMyMTggc1x1YzVkMCBcdWIzMDBcdWQ1NzQgJnF1b3Q7cyBzbGljZXMmcXVvdDsgKFx1YjUzMFx1YzYzNFx1ZDQ1YyBcdWM4MWNcdWM2NzgpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMGFjXHVjNzc0XHVjNWQ0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjZDljXHViODI1XHVjNzU4IFx1YmIzOFx1YmM5NVx1YzgwMSBcdWM2MjRcdWI5NThcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTIwIFx1YzJlMFx1YWNiZFx1YzRmMFx1YzljMCBcdWI5ZDBcdWM3OTAuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MTgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGl6emEhIiwiZGVzY3JpcHRpb24iOiI8cD5GaW5hbGx5LCB3ZSBnZXQgdG8gdGhlIG1vc3QgaW1wb3J0YW50IHBhcnQgb2YgdGhlIGNvbnRlc3Q6IEVhdGluZyB0aGUgcGl6emEuIEJ1dCBldmVuIGhlcmUsIHByb2JsZW1zIGFyZSBsdXJraW5nISBUaGUgcGl6emEgaGFzIGRlbGljaW91cyBzb3kgbnVnZ2V0cyBvbiBpdCwgYnV0IGl0IGlzbiZyc3F1bzt0IGN1dCB5ZXQuIFNvIHdlIGhhdmUgdG8gY3V0IGl0IGludG8gc2xpY2VzLiBUaGVyZSBhcmUgdHdvIGltcG9ydGFudCBjb25zdHJhaW50cyB3ZSBoYXZlIHRvIG1lZXQ6IGV2ZXJ5IHNsaWNlIG11c3QgaGF2ZSB0aGUgc2FtZSBzaXplLCBhbmQgZXZlcnkgc2xpY2UgbXVzdCBoYXZlIHRoZSBzYW1lIG51bWJlciBvZiBzb3kgbnVnZ2V0cyBvbiBpdC4gVG8gbWFrZSB0aGluZ3Mgd29yc2UsIHRoZSBwaXp6YSBpcyBjaXJjdWxhciwgYW5kIHdlIGNhbiBvbmx5IGN1dCBhbG9uZyBhIHN0cmFpZ2h0IGxpbmUgZnJvbSB0aGUgY2VudGVyIG9mIHRoZSBjaXJjbGUgdG8gaXRzIGNpcmN1bWZlcmVuY2UuIEFuZCB3ZSBjYW4gbmV2ZXIgY3V0IHRocm91Z2ggYSBzb3kgbnVnZ2V0LCBpdCBtdXN0IGFsd2F5cyBiZSBvbiBvbmUgc2lkZSBvZiB0aGUgY3V0IG9yIHRoZSBvdGhlci48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIHBvc2l0aW9ucyBvZiB0aGUgc295IG51Z2dldHMsIGRldGVybWluZXMgd2hpY2ggaXMgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHNsaWNlcyBpbnRvIHdoaWNoIHRoZSBwaXp6YSBjYW4gYmUgY3V0IHN1Y2ggdGhhdCBldmVyeSBwaWVjZSBoYXMgdGhlIHNhbWUgc2l6ZSBhbmQgdGhlIHNhbWUgbnVtYmVyIG9mIHNveSBudWdnZXRzIChub3RpY2UgdGhhdCBhIHBpenphIGNhbiBhbHdheXMgYmUgY3V0IGludG8gMSBzbGljZSAmbWRhc2g7IHNvIHRoZXJlIGFsd2F5cyBpcyBhIHNvbHV0aW9uLik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGlzIHRoZSBudW1iZXIgSyBvZiBpbnB1dCBkYXRhIHNldHMsIGZvbGxvd2VkIGJ5IEsgZGF0YSBzZXRzLCBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgZm9ybTo8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBOIG9mIHNveSBudWdnZXRzIG9uIHRoZSBwaXp6YSAoMSAmbGU7IE4gJmxlOyAyMDApLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IE4gbGluZXMsIGRlc2NyaWJpbmcgdGhlIHBvc2l0aW9ucyBvZiB0aGUgc295IG51Z2dldHMuIEVhY2ggcG9zaXRpb24gaXMgZ2l2ZW4gaW4gcG9sYXIgY29vcmRpbmF0ZXMsIG1lYXN1cmVkIGZyb20gdGhlIGNlbnRlciBvZiB0aGUgcGl6emEuIFRoYXQgaXMsIGEgcG9zaXRpb24gaXMgYSBwYWlyICZsZHF1bzsmYWxwaGE7IHImcmRxdW87LCB3aGVyZSAwICZsZTsgJmFscGhhOyAmbHQ7IDImcGk7IGlzIHRoZSBjb3VudGVyY2xvY2t3aXNlIGFuZ2xlIGJldHdlZW4gdGhlIHBvc2l0aXZlIHgtYXhpcyBhbmQgdGhlIGxpbmUgZnJvbSB0aGUgcGl6emEgY2VudGVyIHRvIHRoZSBzb3kgbnVnZ2V0LiAwICZsdDsgciAmbGU7IDEgaXMgdGhlIGRpc3RhbmNlIG9mIHRoZSBudWdnZXQgZnJvbSB0aGUgY2VudGVyIChlYWNoIHBpenphIHdpbGwgaGF2ZSByYWRpdXMgMSkuIFdlIGFzc3VtZSB0aGF0IG51Z2dldHMgYXJlIHBvaW50cywgYW5kIG5vIHR3byBudWdnZXRzIHdpbGwgYmUgbHlpbmcgb24gdGhlIHNhbWUgc3BvdCBvZiB0aGUgcGl6emEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIG91dHB1dCBpdHMgbnVtYmVyLCBmb2xsb3dlZCBieSB0aGUgbWF4aW11bSBudW1iZXIgb2Ygc2xpY2VzIGludG8gd2hpY2ggaXQgY2FuIGJlIGN1dCBhY2NvcmRpbmcgdG8gdGhlIGFib3ZlIHJ1bGVzLiBSZW1lbWJlciB0aGF0IG5vIGN1dCBjYW4gZ28gdGhyb3VnaCBhIHNveSBudWdnZXQuIE91dHB1dCBmb3IgZGlmZmVyZW50IGRhdGEgc2V0cyBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5IGFuIGVtcHR5IGxpbmUuPFwvcD5cclxuIiwiaGludCI6IjxwPkRvbiZyc3F1bzt0IHdvcnJ5IGFib3V0IHRoZSBncmFtbWFyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

University > The USC Programming Contest > Fall 2007 F번