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

문제

무선 센서 네트워크는 여러 개의 센서로 구성된 네트워크를 의미한다. 각 센서는 센서가 위치한 곳의 온도, 소리, 기압 등을 조사한다.

홍준이는 아마존 이산화탄소 측정 단체(Amazon Carbon-dioxide Measurement, 약칭 ACM)에서 프로젝트를 하나 맡았다. 그 프로젝트는, 아마존에 있는 무선 센서 네트워크로 부터 얻은 탄소의 양을 알아내어 최근 10년 동안 국제 화석 연료 사용양을 구한다. 그 사용량은 세계 산소 전달에 중요한 역할을 한다. 아마존의 숲은 매우 커서 홍준이의 역할이 중요하다.

센서들은 유클리드 거리 d 안에 있는 센서들과 통신할 수 있다. 홍준이는 2차원 평면에서 n개의 센서에 대한 좌표가 주어졌을 때, 집합안에 있는 센서들이 서로 직접적으로 통신 가능한 집합의 최대 크기와 그 집합을 구해야 한다.

입력

입력의 첫 줄에는 센서의 개수 n과 센서끼리 직접적으로 통신 가능한 거리 d가 주어진다 (1 ≤ n ≤ 100, 1 ≤ d ≤ 10 000). 센서들의 번호는 1번 부터 n번까지 순서대로 매겨져 있고, 다음 n개의 줄에 센서 번호 순서대로 좌표 x, y가 주어진다 (-10 000 ≤ x, y ≤ 10 000).

출력

첫 줄에 집합 내에 있는 센서들끼리 서로 직접적으로 통신할 수 있는 집합의 최대 크기를 출력하고, 둘째 줄에 그 집합에 있는 센서들의 번호를 출력한다. 만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.

예제 입력 1

4 1
0 0
0 1
1 0
1 1

예제 출력 1

2
1 2
W3sicHJvYmxlbV9pZCI6IjEwMDU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTNjXHVjMTFjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyIsImRlc2NyaXB0aW9uIjoiPHA+XHViYjM0XHVjMTIwIFx1YzEzY1x1YzExYyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWMxM2NcdWMxMWNcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWMxM2NcdWMxMWNcdWIyOTQgXHVjMTNjXHVjMTFjXHVhYzAwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWFjZjNcdWM3NTggXHVjNjI4XHViM2M0LCBcdWMxOGNcdWI5YWMsIFx1YWUzMFx1YzU1NSBcdWI0ZjFcdWM3NDQgXHVjODcwXHVjMGFjXHVkNTVjXHViMmU0LiA8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NlbnNvci5wbmdcIiBzdHlsZT1cImJhY2tncm91bmQtY29sb3I6aW5pdGlhbDsgZmxvYXQ6cmlnaHQ7IG1hcmdpbjowcHggMHB4IDEwcHggMTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNTQ0XHViOWM4XHVjODc0IFx1Yzc3NFx1YzBiMFx1ZDY1NFx1ZDBjNFx1YzE4YyBcdWNlMjFcdWM4MTUgXHViMmU4XHVjY2I0KEFtYXpvbiBDYXJib24tZGlveGlkZSBNZWFzdXJlbWVudCwgXHVjNTdkXHVjZTZkIEFDTSlcdWM1ZDBcdWMxMWMgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViOTdjIFx1ZDU1OFx1YjA5OCBcdWI5ZTFcdWM1NThcdWIyZTQuIFx1YWRmOCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWIyOTQsIFx1YzU0NFx1YjljOFx1Yzg3NFx1YzVkMCBcdWM3ODhcdWIyOTQmbmJzcDtcdWJiMzRcdWMxMjAgXHVjMTNjXHVjMTFjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjg1YyBcdWJkODBcdWQxMzAgXHVjNWJiXHVjNzQwIFx1ZDBjNFx1YzE4Y1x1Yzc1OCBcdWM1OTFcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVjNWI0IFx1Y2Q1Y1x1YWRmYyAxMFx1YjE0NCBcdWIzZDlcdWM1NDggXHVhZDZkXHVjODFjJm5ic3A7XHVkNjU0XHVjMTFkIFx1YzVmMFx1YjhjYyBcdWMwYWNcdWM2YTlcdWM1OTFcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWFkZjggXHVjMGFjXHVjNmE5XHViN2M5XHVjNzQwIFx1YzEzOFx1YWNjNCBcdWMwYjBcdWMxOGMgXHVjODA0XHViMmVjXHVjNWQwIFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWM1ZWRcdWQ1NjBcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM1NDRcdWI5YzhcdWM4NzRcdWM3NTggXHVjMjMyXHVjNzQwIFx1YjllNFx1YzZiMCBcdWNlZTRcdWMxMWMgXHVkNjRkXHVjOTAwXHVjNzc0XHVjNzU4IFx1YzVlZFx1ZDU2MFx1Yzc3NCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzY1x1YzExY1x1YjRlNFx1Yzc0MCBcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzcwXHViOWFjIGQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMxM2NcdWMxMWNcdWI0ZTRcdWFjZmMgXHVkMWI1XHVjMmUwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMFx1YzExYyBuXHVhYzFjXHVjNzU4IFx1YzEzY1x1YzExY1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzlkMVx1ZDU2OVx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMTNjXHVjMTFjXHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM5YzFcdWM4MTFcdWM4MDFcdWM3M2NcdWI4NWMgXHVkMWI1XHVjMmUwJm5ic3A7XHVhYzAwXHViMmE1XHVkNTVjIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVkMDZjXHVhZTMwXHVjNjQwIFx1YWRmOCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzY1x1YzExY1x1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWMxM2NcdWMxMWNcdWIwN2NcdWI5YWMgXHVjOWMxXHVjODExXHVjODAxXHVjNzNjXHViODVjIFx1ZDFiNVx1YzJlMCBcdWFjMDBcdWIyYTVcdWQ1NWMmbmJzcDtcdWFjNzBcdWI5YWMgZFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQmbmJzcDsoMSZuYnNwOyZsZTsgbiZuYnNwOyZsZTsgMTAwLCAxJm5ic3A7JmxlOyBkJm5ic3A7JmxlOyAxMCAwMDApLiBcdWMxM2NcdWMxMWNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJjODggXHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMxM2NcdWMxMWMgXHViYzg4XHVkNjM4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4OGNcdWQ0NWMgeCwgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKC0xMCAwMDAmbmJzcDsmbGU7IHgsIHkmbmJzcDsmbGU7IDEwIDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCZuYnNwO1x1YzlkMVx1ZDU2OSBcdWIwYjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzEzY1x1YzExY1x1YjRlNFx1YjA3Y1x1YjlhYyBcdWMxMWNcdWI4NWMgXHVjOWMxXHVjODExXHVjODAxXHVjNzNjXHViODVjIFx1ZDFiNVx1YzJlMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVkMDZjXHVhZTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjggXHVjOWQxXHVkNTY5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMxM2NcdWMxMWNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTAwNTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZW5zb3IgTmV0d29yayIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZW5zb3IucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE4MXB4OyB3aWR0aDozMjJweFwiIFwvPkEgd2lyZWxlc3Mgc2Vuc29yIG5ldHdvcmsgY29uc2lzdHMgb2YgYXV0b25vbW91cyBzZW5zb3JzIHNjYXR0ZXJlZCBpbiBhbiBlbnZpcm9ubWVudCB3aGVyZSB0aGV5IG1vbml0b3IgY29uZGl0aW9ucyBzdWNoIGFzIHRlbXBlcmF0dXJlLCBzb3VuZCwgYW5kIHByZXNzdXJlLjxcL3A+XHJcblxyXG48cD5TYW1hbnRoYSBpcyBhIHJlc2VhcmNoZXIgd29ya2luZyBvbiB0aGUgQW1hem9uIENhcmJvbi1kaW94aWRlIE1lYXN1cmVtZW50IChBQ00pIHByb2plY3QuIEluIHRoaXMgcHJvamVjdCwgYSB3aXJlbGVzcyBzZW5zb3IgbmV0d29yayBpbiB0aGUgQW1hem9uIHJhaW5mb3Jlc3QgZ2F0aGVycyBlbnZpcm9ubWVudGFsIGluZm9ybWF0aW9uLiBUaGUgQW1hem9uIHJhaW5mb3Jlc3Qgc3RvcmVzIGFuIGFtb3VudCBvZiBjYXJib24gZXF1aXZhbGVudCB0byBhIGRlY2FkZSBvZiBnbG9iYWwgZm9zc2lsIGZ1ZWwgZW1pc3Npb25zLCBhbmQgaXQgcGxheXMgYSBjcnVjaWFsIHJvbGUgaW4gdGhlIHdvcmxkJnJzcXVvO3Mgb3h5Z2VuLXRyYW5zZmVyIHByb2Nlc3Nlcy4gQmVjYXVzZSBvZiB0aGUgaHVnZSBzaXplIG9mIHRoaXMgZm9yZXN0LCBjaGFuZ2VzIGluIHRoZSBmb3Jlc3QgYWZmZWN0IG5vdCBvbmx5IHRoZSBsb2NhbCBlbnZpcm9ubWVudCBidXQgYWxzbyBnbG9iYWwgY2xpbWF0ZSBieSBhbHRlcmluZyB3aW5kIGFuZCBvY2VhbiBjdXJyZW50IHBhdHRlcm5zLiBUaGUgZ29hbCBvZiB0aGUgQUNNIHByb2plY3QgaXMgdG8gaGVscCBzY2llbnRpc3RzIGJldHRlciB1bmRlcnN0YW5kIGVhcnRoJnJzcXVvO3MgY29tcGxleCBlY29zeXN0ZW1zIGFuZCB0aGUgaW1wYWN0IG9mIGh1bWFuIGFjdGl2aXRpZXMuPFwvcD5cclxuXHJcbjxwPlNhbWFudGhhIGhhcyBhbiBpbXBvcnRhbnQgaHlwb3RoZXNpcyBhbmQgdG8gdGVzdCBoZXIgaHlwb3RoZXNpcywgc2hlIG5lZWRzIHRvIGZpbmQgYSBzdWJzZXQgb2Ygc2Vuc29ycyBpbiB3aGljaCBlYWNoIHBhaXIgb2Ygc2Vuc29ycyBjYW4gY29tbXVuaWNhdGUgZGlyZWN0bHkgd2l0aCBlYWNoIG90aGVyLiBBIHNlbnNvciBjYW4gY29tbXVuaWNhdGUgZGlyZWN0bHkgd2l0aCBhbnkgb3RoZXIgc2Vuc29yIGhhdmluZyBkaXN0YW5jZSBhdCBtb3N0IGQgZnJvbSBpdC4gSW4gb3JkZXIgZm9yIGhlciBleHBlcmltZW50cyB0byBiZSBhcyBhY2N1cmF0ZSBhcyBwb3NzaWJsZSwgU2FtYW50aGEgd2FudHMgdG8gY2hvb3NlIGFzIG1hbnkgc2Vuc29ycyBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+QXMgb25lIGRvZXMgbm90IHNpbXBseSB3YWxrIGludG8gdGhlIEFtYXpvbiwgU2FtYW50aGEgY2Fubm90IGFkZCBuZXcgc2Vuc29ycyBvciBtb3ZlIHRob3NlIHRoYXQgYXJlIGN1cnJlbnRseSBpbiBwbGFjZS4gU28gZ2l2ZW4gdGhlIGN1cnJlbnQgbG9jYXRpb25zIG9mIHRoZSBzZW5zb3JzLCBzaGUgbmVlZHMgeW91ciBoZWxwIHRvIGZpbmQgdGhlIGxhcmdlc3Qgc3Vic2V0IHNhdGlzZnlpbmcgaGVyIGNyaXRlcmlhLiBGb3Igc2ltcGxpY2l0eSwgcmVwcmVzZW50IHRoZSBsb2NhdGlvbiBvZiBlYWNoIHNlbnNvciBhcyBhIHBvaW50IGluIGEgdHdvLWRpbWVuc2lvbmFsIHBsYW5lIHdpdGggdGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHBvaW50cyBiZWluZyB0aGUgdXN1YWwgRXVjbGlkZWFuIGRpc3RhbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIHRlc3QgY2FzZS4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIGQgKDEgJmxlOyBuICZsZTsgMTAwIGFuZCAxICZsZTsgZCAmbGU7IDEwIDAwMCksIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBzZW5zb3JzIGF2YWlsYWJsZSBhbmQgZCBpcyB0aGUgbWF4aW11bSBkaXN0YW5jZSBiZXR3ZWVuIHNlbnNvcnMgdGhhdCBjYW4gY29tbXVuaWNhdGUgZGlyZWN0bHkuIFNlbnNvcnMgYXJlIG51bWJlcmVkIDEgdG8gbi4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4IGFuZCB5ICgmbWludXM7MTAgMDAwICZsZTsgeCwgeSAmbGU7IDEwIDAwMCkgaW5kaWNhdGluZyB0aGUgc2Vuc29yIGNvb3JkaW5hdGVzLCBzdGFydGluZyB3aXRoIHRoZSBmaXJzdCBzZW5zb3IuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RGlzcGxheSBhIG1heGltdW0gc3Vic2V0IG9mIHNlbnNvcnMgaW4gd2hpY2ggZWFjaCBwYWlyIG9mIHNlbnNvcnMgY2FuIGNvbW11bmljYXRlIGRpcmVjdGx5LiBUaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGJlIHRoZSBzaXplIG9mIHRoZSBzdWJzZXQuIFRoZSBzZWNvbmQgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGJlIHRoZSAob25lLWJhc2VkKSBpbmRpY2VzIG9mIHRoZSBzZW5zb3JzIGluIHRoZSBzdWJzZXQuIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBzdWNoIHN1YnNldHMsIGFueSBvbmUgb2YgdGhlbSB3aWxsIGJlIGFjY2VwdGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > World Finals > ACM-ICPC World Finals 2014 I번