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

문제

전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을 수록 좋다.

크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다.

입력

첫째 줄에 회로판의 크기 N과 M이 주어진다. (2 ≤ N, M ≤ 100) 

다음 네 줄에는 A1, A2, B1, B2의 좌표가 주어진다. 점의 좌표는 두 정수의 쌍으로 이루어져 있고, 첫 번째 좌표는 0 이상 N 이하이며 두 번째 좌표는 0 이상 M 이하이다. 어떤 점도 같은 위치에 있지 않다.

출력

A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

6 6
2 1
5 4
4 0
4 5

예제 출력 1

15

예제 입력 2

6 3
2 3
4 0
0 2
6 1

예제 출력 2

IMPOSSIBLE
W3sicHJvYmxlbV9pZCI6IjUwMjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjBcdWFjYjAiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29ubmVjdC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTMzcHg7IHdpZHRoOjEyOHB4XCIgXC8+XHVjODA0XHVhZTMwIFx1ZDY4Y1x1Yjg1Y1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwXHVjNzQ0IFx1YzgwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDQgXHViNTRjLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjOWU3XHVjNzQ0IFx1YzIxOFx1Yjg1ZCBcdWM4OGJcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOJnRpbWVzO01cdWM3NzggXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjODEwIEExXHVhY2ZjIEEyLCBcdWFkZjhcdWI5YWNcdWFjZTAgQjFcdWM2NDAgQjJcdWI5N2MgXHVjODA0XHVjMTIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MDRcdWMxMjBcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWMyMThcdWM5YzEsIFx1YzIxOFx1ZDNjOVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzQwIFx1YzgxMVx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4MDRcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODA0XHVjMTIwXHVjNzQwIFx1ZDY4Y1x1Yjg1Y1x1ZDMxMCBcdWJjMTRcdWFlNjVcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY4Y1x1Yjg1Y1x1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOLCBNICZsZTsgMTAwKSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHViMTI0IFx1YzkwNFx1YzVkMFx1YjI5NCBBMSwgQTIsIEIxLCBCMlx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NTggXHVjMzBkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIE4gXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIE0gXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjODEwXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BMVx1YWNmYyBBMiwgXHVhZGY4XHViOWFjXHVhY2UwIEIxXHVhY2ZjIEIyXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTAyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbm5lY3QiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29ubmVjdC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTMzcHg7IG9wYWNpdHk6MC45OyB3aWR0aDoxMjhweFwiIFwvPldoZW4gY29uc3RydWN0aW5nIGVsZWN0cmljIGNpcmN1aXRzIG9uZSBoYXMgdG8gY29ubmVjdCBwYWlycyBvZiBwb2ludHMgdXNpbmcgd2lyZSwgcHJlZmVyYWJsZSBhcyBzaG9ydCBhcyBwb3NzaWJsZS4gSW4gdGhpcyBwcm9ibGVtIHdlIGhhdmUgYW4gZW1wdHkgY2lyY3VpdCBib2FyZCBvZiBzaXplIE4mdGltZXM7TSB3aGVyZSB3ZSB3YW50IHRvIGNvbm5lY3QgdGhlIHR3byBwb2ludHMgQTEgYW5kIEEyIHdpdGggZWFjaCBvdGhlciB1c2luZyBvbmUgd2lyZSwgYW5kIHRoZSB0d28gcG9pbnRzIEIxIGFuZCBCMiB3aXRoIGVhY2ggb3RoZXIgdXNpbmcgYW5vdGhlciB3aXJlLiBUaGUgd2lyZXMgbXVzdCBnbyBhbG9uZyB0aGUgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgZWRnZXMgb2YgdGhlIGdyaWQgKHNlZSBndXJlKSwgYW5kIHRoZSB0d28gd2lyZXMgbWF5IG5vdCBzaGFyZSBhIGNvbW1vbiB2ZXJ0ZXguIERldGVybWluZSB0aGUgbWluaW11bSBsZW5ndGggb2Ygd2lyZSBuZWVkZWQgdG8gZG8gc28uIFRoZSB3aXJlIG1heSBub3QgZ28gb3V0c2lkZSB0aGUgY2lyY3VpdCBib2FyZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgTiAoMiAmbGU7IE4gJmxlOyAxMDApIGFuZCBNICgyICZsZTsgTSAmbGU7IDEwMCksIHRoZSBncmlkIHNpemUgb2YgdGhlIGNpcmN1aXQgYm9hcmQuPFwvcD5cclxuXHJcbjxwPlRoZW4gZm9sbG93cyBmb3VyIGxpbmVzIGNvbnRhaW5pbmcgdGhlIGNvb3JkaW5hdGVzIGZvciB0aGUgcG9pbnRzIEExLCBBMiwgQjEgYW5kIEIyLCByZXNwZWN0aXZlbHkuIEVhY2ggY29vcmRpbmF0ZSBwYWlyIHdpbGwgYmUgZGVzY3JpYmVkIHVzaW5nIHR3byBpbnRlZ2VycyBhbmQgd2lsbCBjb3JyZXNwb25kIHRvIGFuIGludGVyc2VjdGlvbiBwb2ludCBpbiB0aGUgZ3JpZC4gVGhlIHJzdCBjb29yZGluYXRlIHdpbGwgYmUgYmV0d2VlbiAwIGFuZCBOIGluY2x1c2l2ZSBhbmQgdGhlIHNlY29uZCBjb29yZGluYXRlIGJldHdlZW4gMCBhbmQgTSBpbmNsdXNpdmUuIEFsbCBjb29yZGluYXRlIHBhaXJzIHdpbGwgYmUgdW5pcXVlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSBsZW5ndGggb2Ygd2lyZSBuZWVkZWQgdG8gY29ubmVjdCB0aGUgcG9pbnRzLCBvciAmcXVvdDtJTVBPU1NJQkxFJnF1b3Q7IGlmIGl0JiMzOTtzIG5vdCBwb3NzaWJsZSB0byBkbyBzby48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2010 B번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: Green55