시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB42528725972.958%

문제

키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. 각각의 웅덩이는 (Ai, Bi)(|Ai| ≤ 500, |Bi| ≤ 500)에 위치해 있으며 키파는 눈이 좋아 이 웅덩이를 모두 볼 수 있다.

신아가 일찍 일어날 수도 있기 때문에 어서 (X, Y)에 있는 신아의 집에 최대한 빨리 도달해서 그녀가 잘 때 서프라이즈를 해 주고 싶지만, 장화가 새 것이기 때문에 웅덩이를 밟지 않는 것도 중요하다. 만일 키파가 상하좌우로만 이동할 수 있다면 웅덩이를 밟지 않으면서 신아에게 갈 수 있는 최소 거리는 얼마인가? 신아에게 가기 위해 웅덩이를 밟아야만 하는 경우는 없다고 가정한다.

입력

첫째 줄에 X, Y와 N이 공백을 사이에 두고 주어진다.

i+1 (1 ≤ i ≤ N) 번째 줄에 Ai와 Bi가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 키파가 웅덩이를 밟지 않고 신아에게 갈 수 있는 최소 거리를 출력하라.

예제 입력 1

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

예제 출력 1

11

힌트

신아는 (1, 2)에 있다. 키파는 예제 입력에서 주어진 7개의 웅덩이를 모두 볼 수 있다.

   4 . . . . . . . . 
   3 . M . . . . . . 
Y  2 . . M B M . M . 
   1 . M . M . M . . 
   0 . . * . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 
           X

가장 짧은 거리는 아래 그림에서 *로 표시된 길이다.

   4 ******* . . . . 
   3 * M . * . . . . 
Y  2 * . M B M . M . 
   1 * M . M . M . . 
   0 ***** . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 

           X
W3sicHJvYmxlbV9pZCI6IjYxNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWM1NDRcdWI5N2MgXHViOWNjXHViMDk4XHViN2VjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwYTRcdWQzMGNcdWIyOTQgXHVjMmUwXHVjNTQ0XHViOTdjIFx1YjljY1x1YjA5OFx1YjdlYyBcdWM1NDRcdWNlNjggXHVjNzdjXHVjYzBkKFx1YmIzNFx1YjgyNCA2XHVjMmRjXHVjNWQwISkgXHVjNzdjXHVjNWI0XHViMGFjXHViMmU0LiBcdWFjMDRcdWJjMjRcdWM1ZDAgXHVhYzcwXHVjMTNjJm5ic3A7XHViZTQ0XHVhYzAwIFx1YjBiNFx1YjgyNFx1YzExYyZuYnNwO1x1YzBjOFx1Yjg1YyBcdWMwYjAgXHVjN2E1XHVkNjU0XHViOTdjIFx1YzJlMFx1YWNlMCAoMCwgMClcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzlkMVx1Yzc0NCBcdWIwOThcdWMxMjAgXHVkMGE0XHVkMzBjXHViMjk0IFx1YmIzNFx1YjgyNCBOKDEgJmxlOyBOICZsZTsgMTA8c3VwPjQ8XC9zdXA+KVx1YWMxY1x1Yzc1OCBcdWM2YzVcdWIzNjlcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjZjRcdWFjZTAgXHViMTgwXHViNzkwXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNmM1XHViMzY5XHVjNzc0XHViMjk0IChBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4pKHxBPHN1Yj5pPFwvc3ViPnwgJmxlOyA1MDAsIHxCPHN1Yj5pPFwvc3ViPnwgJmxlOyA1MDApXHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU3NCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVkMGE0XHVkMzBjXHViMjk0IFx1YjIwOFx1Yzc3NCBcdWM4OGJcdWM1NDQgXHVjNzc0IFx1YzZjNVx1YjM2OVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1YzU0NFx1YWMwMCBcdWM3N2NcdWNjMGQgXHVjNzdjXHVjNWI0XHViMGEwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzViNFx1YzExYyAoWCwgWSlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJlMFx1YzU0NFx1Yzc1OCBcdWM5ZDFcdWM1ZDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2OFx1YjlhYyZuYnNwO1x1YjNjNFx1YjJlY1x1ZDU3NFx1YzExYyBcdWFkZjhcdWIxNDBcdWFjMDAgXHVjNzk4IFx1YjU0YyZuYnNwO1x1YzExY1x1ZDUwNFx1Yjc3Y1x1Yzc3NFx1Yzk4OFx1Yjk3YyBcdWQ1NzQgXHVjOGZjXHVhY2UwIFx1YzJmNlx1YzljMFx1YjljYywmbmJzcDtcdWM3YTVcdWQ2NTRcdWFjMDAgXHVjMGM4IFx1YWM4M1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNmM1XHViMzY5XHVjNzc0XHViOTdjIFx1YmMxZlx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHViM2M0IFx1YzkxMVx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViOWNjXHVjNzdjIFx1ZDBhNFx1ZDMwY1x1YWMwMCBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjNmM1XHViMzY5XHVjNzc0XHViOTdjIFx1YmMxZlx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVjMmUwXHVjNTQ0XHVjNWQwXHVhYzhjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWFjNzBcdWI5YWNcdWIyOTQgXHVjNWJjXHViOWM4XHVjNzc4XHVhYzAwPyZuYnNwO1x1YzJlMFx1YzU0NFx1YzVkMFx1YWM4YyBcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzZjNVx1YjM2OVx1Yzc3NFx1Yjk3YyBcdWJjMWZcdWM1NDRcdWM1N2NcdWI5Y2MgXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBYLCBZXHVjNjQwJm5ic3A7Tlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmkrMSZuYnNwOygxJm5ic3A7JmxlOyBpICZsZTsgTikgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCZuYnNwO0E8c3ViPmk8XC9zdWI+XHVjNjQwIEI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBhNFx1ZDMwY1x1YWMwMCBcdWM2YzVcdWIzNjlcdWM3NzRcdWI5N2MgXHViYzFmXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWMyZTBcdWM1NDRcdWM1ZDBcdWFjOGMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzJlMFx1YzU0NFx1YjI5NCAoMSwgMilcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWQwYTRcdWQzMGNcdWIyOTQgXHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQmbmJzcDs3XHVhYzFjXHVjNzU4IFx1YzZjNVx1YjM2OVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgIDQgLiAuIC4gLiAuIC4gLiAuIFxyXG4gICAzIC4gTSAuIC4gLiAuIC4gLiBcclxuWSAgMiAuIC4gTSBCIE0gLiBNIC4gXHJcbiAgIDEgLiBNIC4gTSAuIE0gLiAuIFxyXG4gICAwIC4gLiAqIC4gLiAuIC4gLiBcclxuICAtMSAuIC4gLiAuIC4gLiAuIC4gXHJcbiAgICAtMi0xIDAgMSAyIDMgNCA1IFxyXG4gICAgICAgICAgIFhcclxuPFwvcHJlPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyAqXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWFlMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgIDQgKioqKioqKiAuIC4gLiAuIFxyXG4gICAzICogTSAuICogLiAuIC4gLiBcclxuWSAgMiAqIC4gTSBCIE0gLiBNIC4gXHJcbiAgIDEgKiBNIC4gTSAuIE0gLiAuIFxyXG4gICAwICoqKioqIC4gLiAuIC4gLiBcclxuICAtMSAuIC4gLiAuIC4gLiAuIC4gXHJcbiAgICAtMi0xIDAgMSAyIDMgNCA1IFxyXG5cclxuICAgICAgICAgICBYPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYxNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNdWQgUHVkZGxlcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgbGVhdmluZyBoaXMgaG91c2UgcHJvbXB0bHkgYXQgNiBBTSBmb3IgaGlzIGRhaWx5IG1pbGtpbmcgb2YgQmVzc2llLiBIb3dldmVyLCB0aGUgcHJldmlvdXMgZXZlbmluZyBzYXcgYSBoZWF2eSByYWluLCBhbmQgdGhlIGZpZWxkcyBhcmUgcXVpdGUgbXVkZHkuIEZKIHN0YXJ0cyBhdCB0aGUgcG9pbnQgKDAsIDApIGluIHRoZSBjb29yZGluYXRlIHBsYW5lIGFuZCBoZWFkcyB0b3dhcmQgQmVzc2llIHdobyBpcyBsb2NhdGVkIGF0IChYLCBZKSAoLTUwMCAmbHQ7PSBYICZsdDs9IDUwMDsgLTUwMCAmbHQ7PSBZICZsdDs9IDUwMCkuIEhlIGNhbiBzZWUgYWxsIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIHB1ZGRsZXMgb2YgbXVkLCBsb2NhdGVkIGF0IHBvaW50cyAoQV9pLCBCX2kpICgtNTAwICZsdDs9IEFfaSAmbHQ7PSA1MDA7IC01MDAgJmx0Oz0gQl9pICZsdDs9IDUwMCkgb24gdGhlIGZpZWxkLiBFYWNoIHB1ZGRsZSBvY2N1cGllcyBvbmx5IHRoZSBwb2ludCBpdCBpcyBvbi48XC9wPlxyXG5cclxuPHA+SGF2aW5nIGp1c3QgYm91Z2h0IG5ldyBib290cywgRmFybWVyIEpvaG4gYWJzb2x1dGVseSBkb2VzIG5vdCB3YW50IHRvIGRpcnR5IHRoZW0gYnkgc3RlcHBpbmcgaW4gYSBwdWRkbGUsIGJ1dCBoZSBhbHNvIHdhbnRzIHRvIGdldCB0byBCZXNzaWUgYXMgcXVpY2tseSBhcyBwb3NzaWJsZS4gSGUmIzM5O3MgYWxyZWFkeSBsYXRlIGJlY2F1c2UgaGUgaGFkIHRvIGNvdW50IGFsbCB0aGUgcHVkZGxlcy4gSWYgRmFybWVyIEpvaG4gY2FuIG9ubHkgdHJhdmVsIHBhcmFsbGVsIHRvIHRoZSBheGVzIGFuZCB0dXJuIGF0IHBvaW50cyB3aXRoIGludGVnZXIgY29vcmRpbmF0ZXMsIHdoYXQgaXMgdGhlIHNob3J0ZXN0IGRpc3RhbmNlIGhlIG11c3QgdHJhdmVsIHRvIHJlYWNoIEJlc3NpZSBhbmQga2VlcCBoaXMgYm9vdHMgY2xlYW4/IFRoZXJlIHdpbGwgYWx3YXlzIGJlIGEgcGF0aCB3aXRob3V0IG11ZCB0aGF0IEZhcm1lciBKb2huIGNhbiB0YWtlIHRvIHJlYWNoIEJlc3NpZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZSBpbnRlZ2VyczogWCwgWSwgYW5kIE4uPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQV9pIGFuZCBCX2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gZGlzdGFuY2UgdGhhdCBGYXJtZXIgSm9obiBoYXMgdG8gdHJhdmVsIHRvIHJlYWNoIEJlc3NpZSB3aXRob3V0IHN0ZXBwaW5nIGluIG11ZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+QmVzc2llIGlzIGF0ICgxLCAyKS4gRmFybWVyIEpvaG4gc2VlcyA3IG11ZCBwdWRkbGVzLCBsb2NhdGVkIGF0ICgwLCAyKTsgKC0xLCAzKTsgKDMsIDEpOyAoMSwgMSk7ICg0LCAyKTsgKC0xLCAxKSBhbmQgKDIsIDIpLiBQaWN0b3JpYWxseTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgNCAuIC4gLiAuIC4gLiAuIC4gXHJcbiAgIDMgLiBNIC4gLiAuIC4gLiAuIFxyXG5ZICAyIC4gLiBNIEIgTSAuIE0gLiBcclxuICAgMSAuIE0gLiBNIC4gTSAuIC4gXHJcbiAgIDAgLiAuICogLiAuIC4gLiAuIFxyXG4gIC0xIC4gLiAuIC4gLiAuIC4gLiBcclxuICAgIC0yLTEgMCAxIDIgMyA0IDUgXHJcbiAgICAgICAgICAgWDxcL3ByZT5cclxuXHJcbjxwPlRoZSBiZXN0IHBhdGggZm9yIEZhcm1lciBKb2huIGlzICgwLCAwKTsgKC0xLCAwKTsgKC0yLCAwKTsgKC0yLCAxKTsgKC0yLCAyKTsgKC0yLCAzKTsgKC0yLCA0KTsgKC0xLCA0KTsgKDAsIDQpOyAoMCwgMyk7ICgxLCAzKTsgYW5kICgxLCAyKSwgZmluYWxseSByZWFjaGluZyBCZXNzaWUuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgIDQgKioqKioqKiAuIC4gLiAuIFxyXG4gICAzICogTSAuICogLiAuIC4gLiBcclxuWSAgMiAqIC4gTSBCIE0gLiBNIC4gXHJcbiAgIDEgKiBNIC4gTSAuIE0gLiAuIFxyXG4gICAwICoqKioqIC4gLiAuIC4gLiBcclxuICAtMSAuIC4gLiAuIC4gLiAuIC4gXHJcbiAgICAtMi0xIDAgMSAyIDMgNCA1IFxyXG5cclxuICAgICAgICAgICBYPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO December 2007 Contest > Silver 3번

  • 문제를 번역한 사람: kipa00