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

문제

한 도시에 N개의 무선 통신 기지국이 있다. 각각의 기지국의 위치는 x, y 좌표로 표현되며 각 기지국의 좌표는 서로 다르다.
  기지국에서는 특정 주파수의 전파를 이용하여 통신을 한다. 만약 두 기지국의 거리가 20을 넘지 않으면 두 기지국은 인접해 있다고 한다. 인접해 있는 두 기지국은 전파의 방해를 막기 위해 서로 다른 주파수를 사용해야 한다. 또한 주파수가 비슷할 경우 통신 장애가 발생할 수 있기 때문에, 2 이상 차이나야 한다고 하자. 편의상 주파수는 자연수만 고려하자.
  무선 통신 기기를 만들 때에는 가능한 모든 주파수를 다 처리해 주어야 하기 때문에, 사용되는 주파수의 종류수가 적은 편이 유리하다.
  무선 통신 기지국의 위치가 주어졌을 때, 사용되는 주파수의 최소 종류수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤12)이 주어진다. 다음 N개의 줄에는 각 기지국의 좌표가 실수로 주어진다. 입력으로 주어지는 기지국의 위치는 비교적 넓게 퍼져 있어서, 한 기지국에는 최대 4개(물론 자기 자신을 제외하고)의 기지국만 인접해 있다고 가정하자.

출력

첫째 줄에 주파수의 최소 종류수를 출력한다.

예제 입력 1

5
0 0
5 7.5
1 -3
10.75 -20.1
12.01 -22

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjIzNDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWMxMjAgXHVkMWI1XHVjMmUwIFx1YWUzMFx1YzljMFx1YWQ2ZCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgeCwgeSBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViYTcwIFx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPGJyIFwvPlxyXG4mbmJzcDsgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNWQwXHVjMTFjXHViMjk0IFx1ZDJiOVx1YzgxNSBcdWM4ZmNcdWQzMGNcdWMyMThcdWM3NTggXHVjODA0XHVkMzBjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWQxYjVcdWMyZTBcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHViNDUwIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgMjBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWI0NTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMjk0IFx1YjQ1MCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NDAgXHVjODA0XHVkMzBjXHVjNzU4IFx1YmMyOVx1ZDU3NFx1Yjk3YyBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjOGZjXHVkMzBjXHVjMjE4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWM4ZmNcdWQzMGNcdWMyMThcdWFjMDAgXHViZTQ0XHVjMmI3XHVkNTYwIFx1YWNiZFx1YzZiMCBcdWQxYjVcdWMyZTAgXHVjN2E1XHVjNTYwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMiBcdWM3NzRcdWMwYzEgXHVjYzI4XHVjNzc0XHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWM4ZmNcdWQzMGNcdWMyMThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHViOWNjIFx1YWNlMFx1YjgyNFx1ZDU1OFx1Yzc5MC48YnIgXC8+XHJcbiZuYnNwOyBcdWJiMzRcdWMxMjAgXHVkMWI1XHVjMmUwIFx1YWUzMFx1YWUzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHViNTRjXHVjNWQwXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjOGZjXHVkMzBjXHVjMjE4XHViOTdjIFx1YjJlNCBcdWNjOThcdWI5YWNcdWQ1NzQgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBhY1x1YzZhOVx1YjQxOFx1YjI5NCBcdWM4ZmNcdWQzMGNcdWMyMThcdWM3NTggXHVjODg1XHViOTU4XHVjMjE4XHVhYzAwIFx1YzgwMVx1Yzc0MCBcdWQzYjhcdWM3NzQgXHVjNzIwXHViOWFjXHVkNTU4XHViMmU0LjxiciBcLz5cclxuJm5ic3A7IFx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4ODVcdWI5NThcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxJmxlO04mbGU7MTIpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzJlNFx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWJlNDRcdWFkNTBcdWM4MDEgXHViMTEzXHVhYzhjIFx1ZDM3Y1x1YzgzOCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1ZDU1YyBcdWFlMzBcdWM5YzBcdWFkNmRcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIDRcdWFjMWMoXHViYjNjXHViODYwIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwKVx1Yzc1OCBcdWFlMzBcdWM5YzBcdWFkNmRcdWI5Y2MgXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVjODg1XHViOTU4XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzNDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaG9uZSBIb21lIiwiZGVzY3JpcHRpb24iOiI8cD5XaGVuIHJlbGF5IHRvd2VycyBmb3IgbW9iaWxlIHRlbGVwaG9uZXMgY29tbXVuaWNhdGUgd2l0aCB0aGUgbW9iaWxlIHBob25lcyBpbiB0aGVpciBhcmVhLCB0aGVyZSBpcyBhbHdheXMgdGhlIHBvc3NpYmlsaXR5IG9mIGludGVyZmVyZW5jZS4gU28sIHdoZW4gYXNzaWduaW5nIHRoZSB0cmFuc21pc3Npb24gZnJlcXVlbmN5LCB0aGUgRkNDIG1ha2VzIHN1cmUgdGhhdCBuZWFyYnkgdG93ZXJzIGhhdmUgZnJlcXVlbmNpZXMgdGhhdCBhcmVuJiMzOTt0IHRvbyBjbG9zZS4gT24gdGhlIG90aGVyIGhhbmQsIHRoZSBGQ0MgZG9lcyBub3Qgd2FudCB0byBhc3NpZ24gdG9vIG1hbnkgZGlmZmVyZW50IGZyZXF1ZW5jaWVzOyB0aGV5IHdhbnQgdG8gc2F2ZSBhcyBtYW55IGFzIHBvc3NpYmxlIGZvciBvdGhlciB1c2VzLiBZb3VyIGpvYiBpcyB0byBmaW5kIGFuIG9wdGltYWwgYXNzaWdubWVudCBvZiBmcmVxdWVuY2llcy48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB0aGUgZnJlcXVlbmNpZXMgd2lsbCBiZSBpbnRlZ2Vycy4gTmVhcmJ5IHRvd2VycyBtdXN0IGJlIGFzc2lnbmVkIGZyZXF1ZW5jaWVzIHRoYXQgZGlmZmVyIGJ5IGF0IGxlYXN0IDIuIFlvdSYjMzk7bGwgZmluZCBhbiBhc3NpZ25tZW50IHVzaW5nIGFzIGZldyBmcmVxdWVuY2llcyBhcyBwb3NzaWJsZS4gRm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgdHdvIGFycmFuZ2VtZW50cyBvZiB0b3dlcnMuIFR3byB0b3dlcnMgbmVhciBlYWNoIG90aGVyIGFyZSBpbmRpY2F0ZWQgYnkgdGhlIGNvbm5lY3RpbmcgbGluZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waG9uZWhvbWUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyN3B4OyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlIGZvbGxvd2luZyBhcmUgbGVnYWwgZnJlcXVlbmN5IGFzc2lnbm1lbnRzIHRvIHRoZXNlIHR3byB0b3dlciBjb24mbWFjcjtndXJhdGlvbnMuIEhvd2V2ZXIsIHRoZSBzZWNvbmQgYXJyYW5nZW1lbnQgZG9lcyBub3QgdXNlIHRoZSBmZXdlc3QgbnVtYmVyIG9mIGZyZXF1ZW5jaWVzIHBvc3NpYmxlLCBzaW5jZSB0aGUgdG93ZXIgd2l0aCBmcmVxdWVuY3kgNSBjb3VsZCBoYXZlIGZyZXF1ZW5jeSAxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Bob25laG9tZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjM5cHg7IHdpZHRoOjU3NHB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIG11bHRpcGxlIHRlc3QgY2FzZXMuIElucHV0IGZvciBlYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgdHdvIGxpbmVzOiB0aGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdGhlIGludGVnZXIgbiwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRvd2Vycy4gVGhlIG5leHQgbGluZSB3aWxsIGJlIG9mIHRoZSBmb3JtIHgxIHkxIHgyIHkyIC4uLiB4biB5biB3aGVyZSB4aSB5aSBhcmUgdGhlIGNvb3JkaW5hdGVzIG9mIHRvd2VyIGkuIEEgcGFpciBvZiB0b3dlcnMgYXJlIGNvbnNpZGVyZWQgJnF1b3Q7bmVhciZxdW90OyBlYWNoIG90aGVyIGlmIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZW0gaXMgbm8gbW9yZSB0aGFuIDIwLiBUaGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiAxMiB0b3dlcnMgYW5kIG5vIHRvd2VyIHdpbGwgaGF2ZSBtb3JlIHRoYW4gNCB0b3dlcnMgbmVhciBpdC4gQSB2YWx1ZSBvZiBuID0gMCBpbmRpY2F0ZXMgZW5kIG9mIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgeW91IHNob3VsZCBwcmludCBvbmUgbGluZSBpbiB0aGUgZm9ybWF0OjxcL3A+XHJcblxyXG48cD5UaGUgdG93ZXJzIGluIGNhc2UgbiBjYW4gYmUgY292ZXJlZCBpbiBmIGZyZXF1ZW5jaWVzLjxcL3A+XHJcblxyXG48cD53aGVyZSB5b3UgZGV0ZXJtaW5lIHRoZSB2YWx1ZSBmb3IgZi4gVGhlIGNhc2UgbnVtYmVycywgbiwgd2lsbCBzdGFydCBhdCAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==