시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB753360.000%

문제

한 도시에 N개의 무선 통신 기지국이 있다. 각각의 기지국의 위치는 x, y 좌표로 표현되며 각 기지국의 좌표는 서로 다르다.

기지국에서는 특정 주파수의 전파를 이용하여 통신을 한다. 만약 두 기지국의 거리가 20을 넘지 않으면 두 기지국은 인접해 있다고 한다. 인접해 있는 두 기지국은 전파의 방해를 막기 위해 서로 다른 주파수를 사용해야 한다. 또한 주파수가 비슷할 경우 통신 장애가 발생할 수 있기 때문에, 2 이상 차이나야 한다고 하자. 편의상 주파수는 자연수만 고려하자.

무선 통신 기기를 만들 때에는 가능한 모든 주파수를 다 처리해 주어야 하기 때문에, 사용되는 주파수의 종류수가 적은 편이 유리하다.

무선 통신 기지국의 위치가 주어졌을 때, 사용되는 주파수의 최소 종류수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 12)이 주어진다. 다음 N개의 줄에는 각 기지국의 좌표가 실수로 주어진다. 입력으로 주어지는 기지국의 위치는 비교적 넓게 퍼져 있어서, 각 기지국과 인접한 다른 기지국은 최대 4개이다.

기지국의 좌표는 절댓값이 200보다 작거나 같으며, 소숫점 둘째자리까지 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

3

예제 입력 2

6
0 1
19 0
38 1
38 21
19 22
0 21

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjIzNDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWMxMjAgXHVkMWI1XHVjMmUwIFx1YWUzMFx1YzljMFx1YWQ2ZCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgeCwgeSBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViYTcwIFx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzMFx1YzljMFx1YWQ2ZFx1YzVkMFx1YzExY1x1YjI5NCBcdWQyYjlcdWM4MTUgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1YzgwNFx1ZDMwY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVkMWI1XHVjMmUwXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjQ1MCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIDIwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViNDUwIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzQwIFx1YzgwNFx1ZDMwY1x1Yzc1OCBcdWJjMjlcdWQ1NzRcdWI5N2MgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjOGZjXHVkMzBjXHVjMjE4XHVhYzAwIFx1YmU0NFx1YzJiN1x1ZDU2MCBcdWFjYmRcdWM2YjAgXHVkMWI1XHVjMmUwIFx1YzdhNVx1YzU2MFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDIgXHVjNzc0XHVjMGMxIFx1Y2MyOFx1Yzc3NFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWQzYjhcdWM3NThcdWMwYzEgXHVjOGZjXHVkMzBjXHVjMjE4XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVhZTMwXHViOTdjIFx1YjljY1x1YjRlNCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM4ZmNcdWQzMGNcdWMyMThcdWI5N2MgXHViMmU0IFx1Y2M5OFx1YjlhY1x1ZDU3NCBcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGFjXHVjNmE5XHViNDE4XHViMjk0IFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yzc1OCBcdWM4ODVcdWI5NThcdWMyMThcdWFjMDAgXHVjODAxXHVjNzQwIFx1ZDNiOFx1Yzc3NCBcdWM3MjBcdWI5YWNcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzNFx1YzEyMCBcdWQxYjVcdWMyZTAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4ODVcdWI5NThcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4oMSAmbGU7IE4gJmxlOyAxMilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjMmU0XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YmU0NFx1YWQ1MFx1YzgwMSBcdWIxMTNcdWFjOGMgXHVkMzdjXHVjODM4IFx1Yzc4OFx1YzViNFx1YzExYywgXHVhYzAxIFx1YWUzMFx1YzljMFx1YWQ2ZFx1YWNmYyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMmU0XHViOTc4IFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc0MCBcdWNkNWNcdWIzMDAgNFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NzQgMjAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1YzE4Y1x1YzIyYlx1YzgxMCBcdWI0NThcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOGZjXHVkMzBjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4ODVcdWI5NThcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzNDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaG9uZSBIb21lIiwiZGVzY3JpcHRpb24iOiI8cD5XaGVuIHJlbGF5IHRvd2VycyBmb3IgbW9iaWxlIHRlbGVwaG9uZXMgY29tbXVuaWNhdGUgd2l0aCB0aGUgbW9iaWxlIHBob25lcyBpbiB0aGVpciBhcmVhLCB0aGVyZSBpcyBhbHdheXMgdGhlIHBvc3NpYmlsaXR5IG9mIGludGVyZmVyZW5jZS4gU28sIHdoZW4gYXNzaWduaW5nIHRoZSB0cmFuc21pc3Npb24gZnJlcXVlbmN5LCB0aGUgRkNDIG1ha2VzIHN1cmUgdGhhdCBuZWFyYnkgdG93ZXJzIGhhdmUgZnJlcXVlbmNpZXMgdGhhdCBhcmVuJiMzOTt0IHRvbyBjbG9zZS4gT24gdGhlIG90aGVyIGhhbmQsIHRoZSBGQ0MgZG9lcyBub3Qgd2FudCB0byBhc3NpZ24gdG9vIG1hbnkgZGlmZmVyZW50IGZyZXF1ZW5jaWVzOyB0aGV5IHdhbnQgdG8gc2F2ZSBhcyBtYW55IGFzIHBvc3NpYmxlIGZvciBvdGhlciB1c2VzLiBZb3VyIGpvYiBpcyB0byBmaW5kIGFuIG9wdGltYWwgYXNzaWdubWVudCBvZiBmcmVxdWVuY2llcy48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB0aGUgZnJlcXVlbmNpZXMgd2lsbCBiZSBpbnRlZ2Vycy4gTmVhcmJ5IHRvd2VycyBtdXN0IGJlIGFzc2lnbmVkIGZyZXF1ZW5jaWVzIHRoYXQgZGlmZmVyIGJ5IGF0IGxlYXN0IDIuIFlvdSYjMzk7bGwgZmluZCBhbiBhc3NpZ25tZW50IHVzaW5nIGFzIGZldyBmcmVxdWVuY2llcyBhcyBwb3NzaWJsZS4gRm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgdHdvIGFycmFuZ2VtZW50cyBvZiB0b3dlcnMuIFR3byB0b3dlcnMgbmVhciBlYWNoIG90aGVyIGFyZSBpbmRpY2F0ZWQgYnkgdGhlIGNvbm5lY3RpbmcgbGluZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waG9uZWhvbWUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyN3B4OyB3aWR0aDo1NTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlIGZvbGxvd2luZyBhcmUgbGVnYWwgZnJlcXVlbmN5IGFzc2lnbm1lbnRzIHRvIHRoZXNlIHR3byB0b3dlciBjb24mbWFjcjtndXJhdGlvbnMuIEhvd2V2ZXIsIHRoZSBzZWNvbmQgYXJyYW5nZW1lbnQgZG9lcyBub3QgdXNlIHRoZSBmZXdlc3QgbnVtYmVyIG9mIGZyZXF1ZW5jaWVzIHBvc3NpYmxlLCBzaW5jZSB0aGUgdG93ZXIgd2l0aCBmcmVxdWVuY3kgNSBjb3VsZCBoYXZlIGZyZXF1ZW5jeSAxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Bob25laG9tZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjM5cHg7IHdpZHRoOjU3NHB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIG11bHRpcGxlIHRlc3QgY2FzZXMuIElucHV0IGZvciBlYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgdHdvIGxpbmVzOiB0aGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdGhlIGludGVnZXIgbiwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRvd2Vycy4gVGhlIG5leHQgbGluZSB3aWxsIGJlIG9mIHRoZSBmb3JtIHgxIHkxIHgyIHkyIC4uLiB4biB5biB3aGVyZSB4aSB5aSBhcmUgdGhlIGNvb3JkaW5hdGVzIG9mIHRvd2VyIGkuIEEgcGFpciBvZiB0b3dlcnMgYXJlIGNvbnNpZGVyZWQgJnF1b3Q7bmVhciZxdW90OyBlYWNoIG90aGVyIGlmIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZW0gaXMgbm8gbW9yZSB0aGFuIDIwLiBUaGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiAxMiB0b3dlcnMgYW5kIG5vIHRvd2VyIHdpbGwgaGF2ZSBtb3JlIHRoYW4gNCB0b3dlcnMgbmVhciBpdC4gQSB2YWx1ZSBvZiBuID0gMCBpbmRpY2F0ZXMgZW5kIG9mIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgeW91IHNob3VsZCBwcmludCBvbmUgbGluZSBpbiB0aGUgZm9ybWF0OjxcL3A+XHJcblxyXG48cD5UaGUgdG93ZXJzIGluIGNhc2UgbiBjYW4gYmUgY292ZXJlZCBpbiBmIGZyZXF1ZW5jaWVzLjxcL3A+XHJcblxyXG48cD53aGVyZSB5b3UgZGV0ZXJtaW5lIHRoZSB2YWx1ZSBmb3IgZi4gVGhlIGNhc2UgbnVtYmVycywgbiwgd2lsbCBzdGFydCBhdCAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=