시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 93 44 23 44.231%

문제

오늘은 복날이다!

해빈이는 복날을 맞아 순살치킨 파티를 하기 위해 닭을 잡으려고 한다. 하지만 이번에도 쉽게 잡힐까보냐. 용감한 닭 한 마리가 해빈이에게서 도망치려 한다. 닭은 v m/sec의 속도로 이동할 수 있고, (xs, ys)에서 (xt, yt)에 존재하는 벙커까지 이동하면 해빈이에게서 도망칠 수 있다. 하지만 닭이 m분 이상 벙커 밖을 돌아다닌다면 바로 해빈이에게 잡혀 치킨이 되고 말 것이다.

과연 닭은 해빈이에게서 도망칠 수 있을까?

입력

첫 번째 줄에는 닭의 속도 v와 생존 가능 시간 m이 주어진다. 두 번째 줄에는 닭의 시작 위치 xs와 ys가 공백을 사이에 두고 주어지며, 세 번째 줄에는 목적지의 위치 xt, yt가 주어진다.

그 다음부터는 중간 지점에 존재하는 벙커들의 좌표 x y가 주어진다.

모든 단위는 m(미터, meter)이다. 중간 지점에 존재하는 벙커들의 개수는 1,000개 이하이고, 모든 좌표의 범위는 -10,000에서 +10,000이다.

출력

만약 닭이 해빈이에게서 도망치는데 성공한다면, 출력은 "Yes, visiting n other holes."이라고 해야 한다(이때 n은 거쳐야 하는 중간 지점 벙커의 최소 개수이다). 한편 닭의 미래가 처참하다면 "No."를 출력하면 된다.

예제 입력 1

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

예제 출력 1

Yes, visiting 2 other holes.
W3sicHJvYmxlbV9pZCI6IjE2ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjVcdWIwYTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyNFx1YjI5OFx1Yzc0MCBcdWJjZjVcdWIwYTBcdWM3NzRcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWJjZjVcdWIwYTBcdWM3NDQgXHViOWRlXHVjNTQ0Jm5ic3A7XHVjMjFjXHVjMGI0XHVjZTU4XHVkMGE4IFx1ZDMwY1x1ZDJmMFx1Yjk3YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjJlZFx1Yzc0NCBcdWM3YTFcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiZuYnNwO1x1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzRcdWJjODhcdWM1ZDBcdWIzYzQmbmJzcDtcdWMyN2RcdWFjOGMgXHVjN2ExXHVkNzkwXHVhZTRjXHViY2Y0XHViMGQwLiBcdWM2YTlcdWFjMTBcdWQ1NWMgXHViMmVkIFx1ZDU1YyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVkNTc0XHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YjNjNFx1YjlkZFx1Y2U1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuJm5ic3A7XHViMmVkXHVjNzQwIHYgbVwvc2VjXHVjNzU4IFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgKHhzLCB5cylcdWM1ZDBcdWMxMWMgKHh0LCB5dClcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YmM5OVx1Y2VlNFx1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHVkNTc0XHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YjNjNFx1YjlkZFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwO1x1ZDU1OFx1YzljMFx1YjljYyBcdWIyZWRcdWM3NzQgbVx1YmQ4NCBcdWM3NzRcdWMwYzEgXHViYzk5XHVjZWU0IFx1YmMxNlx1Yzc0NCBcdWIzY2NcdWM1NDRcdWIyZTRcdWIyY2NcdWIyZTRcdWJhNzQgXHViYzE0XHViODVjIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM3YTFcdWQ2MDAgXHVjZTU4XHVkMGE4XHVjNzc0IFx1YjQxOFx1YWNlMCBcdWI5ZDAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZmNcdWM1ZjAgXHViMmVkXHVjNzQwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YzVkMFx1YWM4Y1x1YzExYyZuYnNwO1x1YjNjNFx1YjlkZFx1Y2U2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmVkXHVjNzU4IFx1YzE4ZFx1YjNjNCB2XHVjNjQwIFx1YzBkZFx1Yzg3NCBcdWFjMDBcdWIyYTUgXHVjMmRjXHVhYzA0IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlZFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IHhzXHVjNjQwIHlzXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwmbmJzcDtcdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhYTlcdWM4MDFcdWM5YzBcdWM3NTggXHVjNzA0XHVjZTU4IHh0LCB5dFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGNcdWJkODBcdWQxMzBcdWIyOTQgXHVjOTExXHVhYzA0IFx1YzljMFx1YzgxMFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViYzk5XHVjZWU0XHViNGU0XHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4IHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViMmU4XHVjNzA0XHViMjk0IG0oXHViYmY4XHVkMTMwLCZuYnNwO21ldGVyKVx1Yzc3NFx1YjJlNC4mbmJzcDtcdWM5MTFcdWFjMDQgXHVjOWMwXHVjODEwXHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWJjOTlcdWNlZTRcdWI0ZTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEsMDAwXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YWNlMCwgXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWJjOTRcdWM3MDRcdWIyOTQgLTEwLDAwMFx1YzVkMFx1YzExYyArMTAsMDAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCBcdWIyZWRcdWM3NzQgXHVkNTc0XHViZTQ4XHVjNzc0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YjNjNFx1YjlkZFx1Y2U1OFx1YjI5NFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1Y2Q5Y1x1YjgyNVx1Yzc0MCZuYnNwOyZxdW90O1llcywgdmlzaXRpbmcgbiBvdGhlciBob2xlcy4mcXVvdDtcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNChcdWM3NzRcdWI1NGMgblx1Yzc0MCBcdWFjNzBcdWNjZDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzkxMVx1YWMwNCBcdWM5YzBcdWM4MTAgXHViYzk5XHVjZWU0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQpLiZuYnNwO1x1ZDU1Y1x1ZDNiOCBcdWIyZWRcdWM3NTggXHViYmY4XHViNzk4XHVhYzAwIFx1Y2M5OFx1Y2MzOFx1ZDU1OFx1YjJlNFx1YmE3NCAmcXVvdDtOby4mcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR29waGVyIGFuZCBoYXdrcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBnb3BoZXIgc2l0cyBpbiBhIGhvbGUgbG9jYXRlZCBhdCAoeHMsIHlzKSBhbmQgd2FudHMgdG8gZ2V0IHRvIGEgaG9sZSBsb2NhdGVkIGF0ICh4dCwgeXQpLiBUaGUgZ29waGVyIGNhbiBydW4gYXQgYSBjb25zdGFudCBzcGVlZCBvZiB2IG1cL3NlYy4gSG93ZXZlciwgaWYgdGhlIGdvcGhlciBpcyBvdXRzaWRlIG9mIGEgaG9sZSBmb3IgbW9yZSB0aGFuIGEgbSBtaW51dGVzIGhlIHdpbGwgYmVjb21lIGEgc3VwcGVyIHRvIGhhd2tzIGZseWluZyBvdmVyIHRoZSBob2xlcy4gQ2FuIHRoZSBnb3BoZXIgbWFrZSBpdD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VyIG51bWJlcnM6IHYgLS0gZ29waGVyJiMzOTtzIHNwZWVkIGluIG1ldGVycyBwZXIgc2Vjb25kIGFuZCBtIC0tIHRoZSB0aW1lIGFmdGVyIHdoaWNoIHRoZSBnb3BoZXIgYmVjb21lcyBwcmV5IHRvIGhhd2tzIGlmIGhlIHN0YXlzIG91dHNpZGUgYSBob2xlLiBUaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGZsb2F0aW5nIHBvaW50IG51bWJlcnM6IHRoZSAoeHMseXMpIGNvb3JkaW5hdGVzIG9mIHRoZSBnb3BoZXIgc3RhcnRpbmcgaG9sZS4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgdGhlICh4dCwgeXQpIGNvb3JkaW5hdGVzIG9mIHRoZSB0YXJnZXQgaG9sZS4gRWFjaCBTdWJzZXF1ZW50IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGZsb2F0aW5nIHBvaW50IG51bWJlcnM6IHRoZSAoeCx5KSBjb29yZGluYXRlcyBvZiBhIGdvcGhlciBob2xlLiBBbGwgZGlzdGFuY2VzIGFyZSBpbiBtZXRyZXMsIHRvIHRoZSBuZWFyZXN0IG1tLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZSBnb3BoZXIgY2FuIG1ha2UgaXQgdG8gdGhlIHRhcmdldCBob2xlLCB0aGUgb3V0cHV0IGxpbmUgc2hvdWxkIHJlYWQgJnF1b3Q7WWVzLCB2aXNpdGluZyBuIG90aGVyIGhvbGVzLiZxdW90Oywgd2hlcmUgbiBpcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgaW50ZXJtZWRpYXRlIGhvbGVzIHRoZSBnb3BoZXIgaGFzIHRvIHZpc2l0LiBJZiB0aGUgZ29waGVyIGNhbm5vdCBtYWtlIGl0IHRoZSBvdXRwdXQgbGluZSBzaG91bGQgcmVhZCAmcXVvdDtOby4mcXVvdDsgVGhlcmUgYXJlIG5vdCBtb3JlIHRoYW4gMTAwMCBnb3BoZXIgaG9sZXMgYW5kIGFsbCBjb29yZGluYXRlcyBhcmUgYmV0d2VlbiAtMTAwMDAgYW5kICsxMDAwMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > North America > Rocky Mountain Regional > Alberta Collegiate Programming Contest > ACPC 1999 D번

  • 잘못된 데이터를 찾은 사람: appa
  • 문제를 번역한 사람: WeissBlume