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

문제

동주는 매우 훌륭한 예술가이다. 동주는 크고 훌륭한 예술 작품을 만들기를 매우 좋아한다. 그러던 어는 날 동주는 자신의 논에 큰 거미줄 모양의 예술작품을 만들 계획을 세웠다.

동주의 계획은 다음과 같다. 먼저 자신의 논에 N개의 기둥을 세워 커다란 볼록 다각형을 만든 후, 두 기둥에 줄을 연결한다. 그런데 줄을 연결하는데 제약 조건이 있다. 먼저 좀 더 훌륭한 예술 작품이 나오기 위해서 이웃한 두 개의 기둥에는 줄을 연결할 수가 없다. 그리고 줄이 서로 교차하게 되면 나중에 해체할 때 힘들기 때문에 줄이 서로 교차하는 일은 없어야 한다.

그리고 한 가지의 큰 문제점이 있다. 동주의 논은 매우 오랜 시간동안 관리를 하지 않았기 때문에 반지름이 R인 원 모양의 물웅덩이가 G개 있다. 물웅덩이 위로 줄을 연결하는 일은 매우 힘든 일이므로 물웅덩이 위로 줄이 연결되는 일은 없어야 한다. (물웅덩이의 경계를 지나는 경우도 허용되지 않는 것으로 한다.)

동주의 목적은 위의 조건을 만족 하면서 줄을 최대한 많이 연결 하는 것이다. 여러분은 동주를 도와 N개의 기둥의 좌표와 물웅덩이의 반지름 R과 G개의 물웅덩이의 중심 좌표가 주어져 있을 때 몇 개의 줄로 연결할 수 있는지 구하는 프로그램을 작성하여야 한다.

입력

첫째 줄에 기둥의 개수 N(1 ≤ N ≤ 150), 웅덩이의 개수 G(0 ≤ G ≤ 100), 웅덩이들의 반지름 R(1 ≤ R ≤ 100,000)이 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 기둥의 좌표가 주어진다. 그리고 다음 G개의 줄에 걸쳐 웅덩이의 중심의 좌표가 주어진다. 좌표는 0 이상 1,000,000 이하의 정수이다.

입력으로 주어지는 좌표는 모두 다르다.

출력

첫 줄에 연결할 수 있는 최대 줄의 개수를 출력한다.

예제 입력 1

5 3 1
6 10
10 7
9 1
2 0
0 3
2 2
5 6
8 3

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjE4NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWJiZjhcdWM5MDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1YzhmY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVkNmNjXHViOTZkXHVkNTVjIFx1YzYwOFx1YzIyMFx1YWMwMFx1Yzc3NFx1YjJlNC4gXHViM2Q5XHVjOGZjXHViMjk0ICBcdWQwNmNcdWFjZTAgXHVkNmNjXHViOTZkXHVkNTVjIFx1YzYwOFx1YzIyMCBcdWM3OTFcdWQ0ODhcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwXHViOTdjIFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjM1OCBcdWM1YjRcdWIyOTQgXHViMGEwIFx1YjNkOVx1YzhmY1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHViMTdjXHVjNWQwIFx1ZDA3MCBcdWFjNzBcdWJiZjhcdWM5MDQgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzYwOFx1YzIyMFx1Yzc5MVx1ZDQ4OFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzEzOFx1YzZlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVjOGZjXHVjNzU4IFx1YWNjNFx1ZDY4ZFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWJhM2NcdWM4MDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YjE3Y1x1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YWUzMFx1YjQ2NVx1Yzc0NCBcdWMxMzhcdWM2Y2MgXHVjZWU0XHViMmU0XHViNzgwIFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGUwIFx1ZDZjNCwgXHViNDUwIFx1YWUzMFx1YjQ2NVx1YzVkMCBcdWM5MDRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjOTA0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYTNjXHVjODAwIFx1Yzg4MCBcdWIzNTQgXHVkNmNjXHViOTZkXHVkNTVjIFx1YzYwOFx1YzIyMCBcdWM3OTFcdWQ0ODhcdWM3NzQgXHViMDk4XHVjNjI0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM3NzRcdWM2YzNcdWQ1NWMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFlMzBcdWI0NjVcdWM1ZDBcdWIyOTQgXHVjOTA0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjOTA0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0IFx1YjA5OFx1YzkxMVx1YzVkMCBcdWQ1NzRcdWNjYjRcdWQ1NjAgXHViNTRjIFx1ZDc5OFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjOTA0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YzVjNlx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ1NWMgXHVhYzAwXHVjOWMwXHVjNzU4IFx1ZDA3MCBcdWJiMzhcdWM4MWNcdWM4MTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWIzZDlcdWM4ZmNcdWM3NTggXHViMTdjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM2MjRcdWI3OWMgXHVjMmRjXHVhYzA0XHViM2Q5XHVjNTQ4IFx1YWQwMFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgUlx1Yzc3OCBcdWM2ZDAgXHViYWE4XHVjNTkxXHVjNzU4IFx1YmIzY1x1YzZjNVx1YjM2OVx1Yzc3NFx1YWMwMCBHXHVhYzFjIFx1Yzc4OFx1YjJlNC4gIFx1YmIzY1x1YzZjNVx1YjM2OVx1Yzc3NCBcdWM3MDRcdWI4NWMgXHVjOTA0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDAgXHViOWU0XHVjNmIwIFx1ZDc5OFx1YjRlMCBcdWM3N2NcdWM3NzRcdWJiYzBcdWI4NWMgXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0IFx1YzcwNFx1Yjg1YyBcdWM5MDRcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWM5YzBcdWIwOThcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1ZDVjOFx1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1ZDU1Y1x1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1YzhmY1x1Yzc1OCBcdWJhYTlcdWM4MDFcdWM3NDAgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzEgXHVkNTU4XHViYTc0XHVjMTFjIFx1YzkwNFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1YzVmMFx1YWNiMCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHViM2Q5XHVjOGZjXHViOTdjIFx1YjNjNFx1YzY0MCBOXHVhYzFjXHVjNzU4IFx1YWUzMFx1YjQ2NVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NCBSXHVhY2ZjIEdcdWFjMWNcdWM3NTggXHViYjNjXHVjNmM1XHViMzY5XHVjNzc0XHVjNzU4IFx1YzkxMVx1YzJlYyBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFlMzBcdWI0NjVcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxNTApLCBcdWM2YzVcdWIzNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IEcoMCAmbGU7IEcgJmxlOyAxMDApLCBcdWM2YzVcdWIzNjlcdWM3NzRcdWI0ZTRcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0IFIoMSAmbGU7IFIgJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YWUzMFx1YjQ2NVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHVjNzRjIEdcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM2YzVcdWIzNjlcdWM3NzRcdWM3NTggXHVjOTExXHVjMmVjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM5MDRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUm9waW5nIHRoZSBGaWVsZCIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgcXVpdGUgdGhlIG5hdHVyZSBhcnRpc3Q6IGhlIG9mdGVuIGNvbnN0cnVjdHMgbGFyZ2Ugd29ya3Mgb2YgYXJ0IG9uIGhpcyBmYXJtLiBUb2RheSwgRkogd2FudHMgdG8gY29uc3RydWN0IGEgZ2lhbnQgJnF1b3Q7ZmllbGQgd2ViJnF1b3Q7LiBGSiYjMzk7cyBmaWVsZCBpcyBsYXJnZSBjb252ZXggcG9seWdvbiB3aXRoIGZlbmNlcyBhbG9uZyB0aGUgYm91bmRhcnkgYW5kIGZlbmNlIHBvc3RzIGF0IGVhY2ggb2YgdGhlIE4gY29ybmVycyAoMSAmbHQ7PSBOICZsdDs9IDE1MCkuIFRvIGNvbnN0cnVjdCBoaXMgZmllbGQgd2ViLCBGSiB3YW50cyB0byBydW4gYXMgbWFueSByb3BlcyBhcyBwb3NzaWJsZSBpbiBzdHJhaWdodCBsaW5lcyBiZXR3ZWVuIHBhaXJzIG9mIG5vbi1hZGphY2VudCBmZW5jZSBwb3N0cyBzdWNoIHRoYXQgbm8gdHdvIHJvcGVzIGNyb3NzLjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBvbmUgY29tcGxpY2F0aW9uOiBGSiYjMzk7cyBmaWVsZCBpcyBub3QgY29tcGxldGVseSB1c2FibGUuIFNvbWUgZXZpbCBhbGllbnMgaGF2ZSBjcmVhdGVkIGEgdG90YWwgb2YgRyAoMCAmbHQ7PSBHICZsdDs9IDEwMCkgZ3JhaW4gY2lyY2xlcyBpbiB0aGUgZmllbGQsIGFsbCBvZiByYWRpdXMgUiAoMSAmbHQ7PSBSICZsdDs9IDEwMCwwMDApLiBGSiBpcyBhZnJhaWQgdG8gdXBzZXQgdGhlIGFsaWVucywgYW5kIHRoZXJlZm9yZSBkb2VzbiYjMzk7dCB3YW50IHRoZSByb3BlcyB0byBwYXNzIHRocm91Z2gsIG9yIGV2ZW4gdG91Y2ggdGhlIHZlcnkgZWRnZSBvZiBhIGdyYWluIGNpcmNsZS4gTm90ZSB0aGF0IGFsdGhvdWdoIHRoZSBjZW50ZXJzIG9mIGFsbCB0aGUgY2lyY2xlcyBhcmUgY29udGFpbmVkIHdpdGhpbiB0aGUgZmllbGQsIGEgd2lkZSByYWRpdXMgbWF5IG1ha2UgaXQgZXh0ZW5kIG91dHNpZGUgb2YgdGhlIGZpZWxkLCBhbmQgYm90aCBmZW5jZXMgYW5kIGZlbmNlIHBvc3RzIG1heSBiZSB3aXRoaW4gYSBncmFpbiBjaXJjbGUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBsb2NhdGlvbnMgb2YgdGhlIGZlbmNlIHBvc3RzIGFuZCB0aGUgY2VudGVycyBvZiB0aGUgY2lyY2xlcywgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiByb3BlcyB0aGF0IEZKIGNhbiB1c2UgdG8gY3JlYXRlIGhpcyBmaWVsZCB3ZWIuPFwvcD5cclxuXHJcbjxwPkZKJiMzOTtzIGZlbmNlIHBvdHMgYW5kIHRoZSBjaXJjbGUgY2VudGVycyBhbGwgaGF2ZSBpbnRlZ2VyIGNvb3JkaW5hdGVzIFggYW5kIFkgZWFjaCBvZiB3aGljaCBpcyBpbiB0aGUgcmFuZ2UgMC4uMSwwMDAsMDAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiwgRywgYW5kIFI8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB0aGF0IGFyZSB0aGUgWCxZIHBvc2l0aW9uIG9mIGEgZmVuY2UgcG9zdCBvbiB0aGUgYm91bmRhcnkgb2YgRkomIzM5O3MgZmllbGQuPFwvbGk+XHJcblx0PGxpPkxpbmVzIE4rMi4uTitHKzE6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgYXJlIHRoZSBYLFkgcG9zaXRpb24gb2YgYSBjaXJjbGUmIzM5O3MgY2VudGVyIGluc2lkZSBGSiYjMzk7cyBmaWVsZC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHJvcGVzIEZKIGNhbiB1c2UgZm9yIGhpcyBhcnRpc3RpYyBjcmVhdGlvbi48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO January 2006 Contest > Gold ?번