시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 21 6 6 75.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+XHJcbiZuYnNwOyBcdWJiMzRcdWMxMjAgXHVkMWI1XHVjMmUwIFx1YWUzMFx1YWUzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHViNTRjXHVjNWQwXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjOGZjXHVkMzBjXHVjMjE4XHViOTdjIFx1YjJlNCBcdWNjOThcdWI5YWNcdWQ1NzQgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBhY1x1YzZhOVx1YjQxOFx1YjI5NCBcdWM4ZmNcdWQzMGNcdWMyMThcdWM3NTggXHVjODg1XHViOTU4XHVjMjE4XHVhYzAwIFx1YzgwMVx1Yzc0MCBcdWQzYjhcdWM3NzQgXHVjNzIwXHViOWFjXHVkNTU4XHViMmU0LjxiciBcLz5cclxuJm5ic3A7IFx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4ODVcdWI5NThcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxJmxlO04mbGU7MTIpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzJlNFx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWJlNDRcdWFkNTBcdWM4MDEgXHViMTEzXHVhYzhjIFx1ZDM3Y1x1YzgzOCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1ZDU1YyBcdWFlMzBcdWM5YzBcdWFkNmRcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIDRcdWFjMWMoXHViYjNjXHViODYwIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwKVx1Yzc1OCBcdWFlMzBcdWM5YzBcdWFkNmRcdWI5Y2MgXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVjODg1XHViOTU4XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM0OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBob25lIEhvbWUiLCJkZXNjcmlwdGlvbiI6IjxwPldoZW4gcmVsYXkgdG93ZXJzIGZvciBtb2JpbGUgdGVsZXBob25lcyBjb21tdW5pY2F0ZSB3aXRoIHRoZSBtb2JpbGUgcGhvbmVzIGluIHRoZWlyIGFyZWEsIHRoZXJlIGlzIGFsd2F5cyB0aGUgcG9zc2liaWxpdHkgb2YgaW50ZXJmZXJlbmNlLiBTbywgd2hlbiBhc3NpZ25pbmcgdGhlIHRyYW5zbWlzc2lvbiBmcmVxdWVuY3ksIHRoZSBGQ0MgbWFrZXMgc3VyZSB0aGF0IG5lYXJieSB0b3dlcnMgaGF2ZSBmcmVxdWVuY2llcyB0aGF0IGFyZW4mIzM5O3QgdG9vIGNsb3NlLiBPbiB0aGUgb3RoZXIgaGFuZCwgdGhlIEZDQyBkb2VzIG5vdCB3YW50IHRvIGFzc2lnbiB0b28gbWFueSBkaWZmZXJlbnQgZnJlcXVlbmNpZXM7IHRoZXkgd2FudCB0byBzYXZlIGFzIG1hbnkgYXMgcG9zc2libGUgZm9yIG90aGVyIHVzZXMuIFlvdXIgam9iIGlzIHRvIGZpbmQgYW4gb3B0aW1hbCBhc3NpZ25tZW50IG9mIGZyZXF1ZW5jaWVzLjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHRoZSBmcmVxdWVuY2llcyB3aWxsIGJlIGludGVnZXJzLiBOZWFyYnkgdG93ZXJzIG11c3QgYmUgYXNzaWduZWQgZnJlcXVlbmNpZXMgdGhhdCBkaWZmZXIgYnkgYXQgbGVhc3QgMi4gWW91JiMzOTtsbCBmaW5kIGFuIGFzc2lnbm1lbnQgdXNpbmcgYXMgZmV3IGZyZXF1ZW5jaWVzIGFzIHBvc3NpYmxlLiBGb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIGZvbGxvd2luZyB0d28gYXJyYW5nZW1lbnRzIG9mIHRvd2Vycy4gVHdvIHRvd2VycyBuZWFyIGVhY2ggb3RoZXIgYXJlIGluZGljYXRlZCBieSB0aGUgY29ubmVjdGluZyBsaW5lLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Bob25laG9tZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IHdpZHRoOjU1N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCB0aGUgZm9sbG93aW5nIGFyZSBsZWdhbCBmcmVxdWVuY3kgYXNzaWdubWVudHMgdG8gdGhlc2UgdHdvIHRvd2VyIGNvbiZtYWNyO2d1cmF0aW9ucy4gSG93ZXZlciwgdGhlIHNlY29uZCBhcnJhbmdlbWVudCBkb2VzIG5vdCB1c2UgdGhlIGZld2VzdCBudW1iZXIgb2YgZnJlcXVlbmNpZXMgcG9zc2libGUsIHNpbmNlIHRoZSB0b3dlciB3aXRoIGZyZXF1ZW5jeSA1IGNvdWxkIGhhdmUgZnJlcXVlbmN5IDEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGhvbmVob21lMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMzlweDsgd2lkdGg6NTc0cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgbXVsdGlwbGUgdGVzdCBjYXNlcy4gSW5wdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHdpbGwgY29uc2lzdCBvZiB0d28gbGluZXM6IHRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiB0aGUgaW50ZWdlciBuLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgdG93ZXJzLiBUaGUgbmV4dCBsaW5lIHdpbGwgYmUgb2YgdGhlIGZvcm0geDEgeTEgeDIgeTIgLi4uIHhuIHluIHdoZXJlIHhpIHlpIGFyZSB0aGUgY29vcmRpbmF0ZXMgb2YgdG93ZXIgaS4gQSBwYWlyIG9mIHRvd2VycyBhcmUgY29uc2lkZXJlZCAmcXVvdDtuZWFyJnF1b3Q7IGVhY2ggb3RoZXIgaWYgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlbSBpcyBubyBtb3JlIHRoYW4gMjAuIFRoZXJlIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDEyIHRvd2VycyBhbmQgbm8gdG93ZXIgd2lsbCBoYXZlIG1vcmUgdGhhbiA0IHRvd2VycyBuZWFyIGl0LiBBIHZhbHVlIG9mIG4gPSAwIGluZGljYXRlcyBlbmQgb2YgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB5b3Ugc2hvdWxkIHByaW50IG9uZSBsaW5lIGluIHRoZSBmb3JtYXQ6PFwvcD5cclxuXHJcbjxwPlRoZSB0b3dlcnMgaW4gY2FzZSBuIGNhbiBiZSBjb3ZlcmVkIGluIGYgZnJlcXVlbmNpZXMuPFwvcD5cclxuXHJcbjxwPndoZXJlIHlvdSBkZXRlcm1pbmUgdGhlIHZhbHVlIGZvciBmLiBUaGUgY2FzZSBudW1iZXJzLCBuLCB3aWxsIHN0YXJ0IGF0IDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=