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

문제

화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어서 더이상 다른 나라들이 얼씬도 못하게 만들 것이다!

그러나 이 방벽은 만들기 까다롭기에 가능한 한 적게 지어야 하며, 자국민들에게도 악영향을 끼칠 수 있으므로 자국의 모든 건물들로부터 L 이상의 거리를 유지해야만 한다.

자국의 건물들의 좌표가 주어졌을 때, 모든 건물들로부터 L 이상의 거리를 두면서 모든 건물을 한번에 두르는 방벽의 최소 길이를 구하시오.

입력

첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수)

다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌표는 다르며, 건물은 충분히 작아서 점과 같다고 생각해도 좋다. 방벽은 자신들끼리 교차해서는 안 되며 끊어져서도 안 된다.

출력

첫째 줄에 답을 정수 단위로 반올림하여 출력한다.

예제 입력 1

9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

예제 출력 1

1628
W3sicHJvYmxlbV9pZCI6Ijc0MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZjlcdWIzYzUgXHViYzI5XHViY2JkIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2U4YjFkNTdkLWVlOGUtNGUyZC1iZjJiLTZlNzg4Nzc2YzU1M1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJtYXJnaW4tbGVmdDogMTBweDsgZmxvYXQ6IHJpZ2h0O1wiIFwvPlx1ZDY1NFx1ZDU1OSZuYnNwO1x1YzgxY1x1YWQ2ZFx1Yzc1OCBcdWM2NTUgXHVjMTMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YWNjNFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWM3NzRcdWM2YzNcdWIwOThcdWI3N2NcdWM3NTggXHVjZTY4XHViYzk0XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1Yzc5MFx1YzcyMFx1Yjg1Y1x1YzZjY1x1YzljMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzkwXHVhZDZkXHVjNzU4IFx1Yzc5MFx1Yjc5MSA8c3Ryb25nPlx1ZDY1NFx1ZDU1OSBcdWJjMjlcdWJjYmQ8XC9zdHJvbmc+XHVjNzQ0IFx1YWM3NFx1YzEyNFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWI5YzhcdWM3NGNcdWJhMzlcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWJjMjlcdWJjYmRcdWM3NDAgXHVhZGZjXHVjYzk4XHVjNWQwIFx1YjJlNFx1YWMwMFx1YzYyNFx1YjI5NCBcdWMwZGRcdWJhODVcdWNjYjRcdWM1ZDBcdWFjOGMgXHVkNTc0XHViODVjXHVjNmI0IFx1YjNjNVx1YzEzMVx1Yzc0NCBcdWIwYjRcdWJmZGNcdWM1YjRcdWMxMWMgXHViMzU0XHVjNzc0XHVjMGMxIFx1YjJlNFx1Yjk3OCBcdWIwOThcdWI3N2NcdWI0ZTRcdWM3NzQgXHVjNWJjXHVjNTJjXHViM2M0IFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0ITxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWIwOTggXHVjNzc0IFx1YmMyOVx1YmNiZFx1Yzc0MCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVhZTRjXHViMmU0XHViODZkXHVhZTMwXHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjODAxXHVhYzhjIFx1YzljMFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Yzc5MFx1YWQ2ZFx1YmJmY1x1YjRlNFx1YzVkMFx1YWM4Y1x1YjNjNCBcdWM1NDVcdWM2MDFcdWQ1YTVcdWM3NDQgXHViMDdjXHVjZTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNzkwXHVhZDZkXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFjNzRcdWJiM2NcdWI0ZTRcdWI4NWNcdWJkODBcdWQxMzAgTCBcdWM3NzRcdWMwYzFcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YzcyMFx1YzljMFx1ZDU3NFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YWQ2ZFx1Yzc1OCBcdWFjNzRcdWJiM2NcdWI0ZTRcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWFjNzRcdWJiM2NcdWI0ZTRcdWI4NWNcdWJkODBcdWQxMzAgTCBcdWM3NzRcdWMwYzFcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YjQ1MFx1YmE3NFx1YzExYyBcdWJhYThcdWI0ZTAmbmJzcDtcdWFjNzRcdWJiM2NcdWM3NDQgXHVkNTVjXHViYzg4XHVjNWQwJm5ic3A7XHViNDUwXHViOTc0XHViMjk0IFx1YmMyOVx1YmNiZFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWFjNzBcdWI5YWMgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDMgJmxlOyBOICZsZTsgMTAwMCwmbmJzcDsxICZsZTsgTCAmbGU7IDEwMDAsIE5cdWFjZmMgTFx1Yzc0MCBcdWM4MTVcdWMyMTgpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzBcdWNjZDAgXHVhYzc0XHViYjNjXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBYPHN1Yj5pPFwvc3ViPlx1YzY0MCBZPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygtMTAwMDAgJmxlOyBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwMDAwKSBcdWJhYThcdWI0ZTAgXHVhYzc0XHViYjNjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWIyZTRcdWI5NzRcdWJhNzAsIFx1YWM3NFx1YmIzY1x1Yzc0MCBcdWNkYTlcdWJkODRcdWQ3ODggXHVjNzkxXHVjNTQ0XHVjMTFjIFx1YzgxMFx1YWNmYyBcdWFjMTlcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC4gXHViYzI5XHViY2JkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1YjRlNFx1YjA3Y1x1YjlhYyBcdWFkNTBcdWNjMjhcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxOFx1YmE3MCBcdWIwNGFcdWM1YjRcdWM4MzhcdWMxMWNcdWIzYzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWM4MTVcdWMyMTggXHViMmU4XHVjNzA0XHViODVjIFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzQyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldhbGwiLCJkZXNjcmlwdGlvbiI6IjxwPk9uY2UgdXBvbiBhIHRpbWUgdGhlcmUgd2FzIGEgZ3JlZWR5IEtpbmcgd2hvIG9yZGVyZWQgaGlzIGNoaWVmIEFyY2hpdGVjdCB0byBidWlsZCBhIHdhbGwgYXJvdW5kIHRoZSBLaW5nJiMzOTtzIGNhc3RsZS4gVGhlIEtpbmcgd2FzIHNvIGdyZWVkeSwgdGhhdCBoZSB3b3VsZCBub3QgbGlzdGVuIHRvIGhpcyBBcmNoaXRlY3QmIzM5O3MgcHJvcG9zYWxzIHRvIGJ1aWxkIGEgYmVhdXRpZnVsIGJyaWNrIHdhbGwgd2l0aCBhIHBlcmZlY3Qgc2hhcGUgYW5kIG5pY2UgdGFsbCB0b3dlcnMuIEluc3RlYWQsIGhlIG9yZGVyZWQgdG8gYnVpbGQgdGhlIHdhbGwgYXJvdW5kIHRoZSB3aG9sZSBjYXN0bGUgdXNpbmcgdGhlIGxlYXN0IGFtb3VudCBvZiBzdG9uZSBhbmQgbGFib3IsIGJ1dCBkZW1hbmRlZCB0aGF0IHRoZSB3YWxsIHNob3VsZCBub3QgY29tZSBjbG9zZXIgdG8gdGhlIGNhc3RsZSB0aGFuIGEgY2VydGFpbiBkaXN0YW5jZS4gSWYgdGhlIEtpbmcgZmluZHMgdGhhdCB0aGUgQXJjaGl0ZWN0IGhhcyB1c2VkIG1vcmUgcmVzb3VyY2VzIHRvIGJ1aWxkIHRoZSB3YWxsIHRoYW4gaXQgd2FzIGFic29sdXRlbHkgbmVjZXNzYXJ5IHRvIHNhdGlzZnkgdGhvc2UgcmVxdWlyZW1lbnRzLCB0aGVuIHRoZSBBcmNoaXRlY3Qgd2lsbCBsb29zZSBoaXMgaGVhZC4gTW9yZW92ZXIsIGhlIGRlbWFuZGVkIEFyY2hpdGVjdCB0byBpbnRyb2R1Y2UgYXQgb25jZSBhIHBsYW4gb2YgdGhlIHdhbGwgbGlzdGluZyB0aGUgZXhhY3QgYW1vdW50IG9mIHJlc291cmNlcyB0aGF0IGFyZSBuZWVkZWQgdG8gYnVpbGQgdGhlIHdhbGwuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBoZWxwIHBvb3IgQXJjaGl0ZWN0IHRvIHNhdmUgaGlzIGhlYWQsIGJ5IHdyaXRpbmcgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGxlbmd0aCBvZiB0aGUgd2FsbCB0aGF0IGhlIGNvdWxkIGJ1aWxkIGFyb3VuZCB0aGUgY2FzdGxlIHRvIHNhdGlzZnkgS2luZyYjMzk7cyByZXF1aXJlbWVudHMuPFwvcD5cclxuXHJcbjxwPlRoZSB0YXNrIGlzIHNvbWV3aGF0IHNpbXBsaWZpZWQgYnkgdGhlIGZhY3QsIHRoYXQgdGhlIEtpbmcmIzM5O3MgY2FzdGxlIGhhcyBhIHBvbHlnb25hbCBzaGFwZSBhbmQgaXMgc2l0dWF0ZWQgb24gYSBmbGF0IGdyb3VuZC4gVGhlIEFyY2hpdGVjdCBoYXMgYWxyZWFkeSBlc3RhYmxpc2hlZCBhIENhcnRlc2lhbiBjb29yZGluYXRlIHN5c3RlbSBhbmQgaGFzIHByZWNpc2VseSBtZWFzdXJlZCB0aGUgY29vcmRpbmF0ZXMgb2YgYWxsIGNhc3RsZSYjMzk7cyB2ZXJ0aWNlcyBpbiBmZWV0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBOIGFuZCBMIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBOICgzICZsZTsgTiAmbGU7IDEwMDApIGlzIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIEtpbmcmIzM5O3MgY2FzdGxlLCBhbmQgTCAoMSAmbGU7IEwgJmxlOyAxMDAwKSBpcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgZmVldCB0aGF0IEtpbmcgYWxsb3dzIGZvciB0aGUgd2FsbCB0byBjb21lIGNsb3NlIHRvIHRoZSBjYXN0bGUuPFwvcD5cclxuXHJcbjxwPk5leHQgTiBsaW5lcyBkZXNjcmliZSBjb29yZGluYXRlcyBvZiBjYXN0bGUmIzM5O3MgdmVydGljZXMgaW4gYSBjbG9ja3dpc2Ugb3JkZXIuIEVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlciBudW1iZXJzIFg8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzcGFjZSAoLTEwMDAwICZsZTsgWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDApIHRoYXQgcmVwcmVzZW50IHRoZSBjb29yZGluYXRlcyBvZiBpdGggdmVydGV4LiBBbGwgdmVydGljZXMgYXJlIGRpZmZlcmVudCBhbmQgdGhlIHNpZGVzIG9mIHRoZSBjYXN0bGUgZG8gbm90IGludGVyc2VjdCBhbnl3aGVyZSBleGNlcHQgZm9yIHZlcnRpY2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPldyaXRlIHRvIHRoZSBvdXRwdXQgZmlsZSB0aGUgc2luZ2xlIG51bWJlciB0aGF0IHJlcHJlc2VudHMgdGhlIG1pbmltYWwgcG9zc2libGUgbGVuZ3RoIG9mIHRoZSB3YWxsIGluIGZlZXQgdGhhdCBjb3VsZCBiZSBidWlsdCBhcm91bmQgdGhlIGNhc3RsZSB0byBzYXRpc2Z5IEtpbmcmIzM5O3MgcmVxdWlyZW1lbnRzLiBZb3UgbXVzdCBwcmVzZW50IHRoZSBpbnRlZ2VyIG51bWJlciBvZiBmZWV0IHRvIHRoZSBLaW5nLCBiZWNhdXNlIHRoZSBmbG9hdGluZyBudW1iZXJzIGFyZSBub3QgaW52ZW50ZWQgeWV0LiBIb3dldmVyLCB5b3UgbXVzdCByb3VuZCB0aGUgcmVzdWx0IGluIHN1Y2ggYSB3YXksIHRoYXQgaXQgaXMgYWNjdXJhdGUgdG8gOCBpbmNoZXMgKDEgZm9vdCBpcyBlcXVhbCB0byAxMiBpbmNoZXMpLCBzaW5jZSB0aGUgS2luZyB3aWxsIG5vdCB0b2xlcmF0ZSBsYXJnZXIgZXJyb3IgaW4gdGhlIGVzdGltYXRlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2001 D번

  • 문제를 번역한 사람: kks227
  • 데이터를 추가한 사람: orihehe
  • 빠진 조건을 찾은 사람: rdd6584