연결
시간 제한1초메모리 제한128 MB
N x M 격자 위에서 A1과 A2를 잇는 선과 B1과 B2를 잇는 선을 서로 만나지 않게 놓을 때, 두 선 길이의 합의 최솟값을 구한다.
문제
전기 회로에서 두 점을 전선으로 이을 때, 전선은 짧을수록 좋다.
크기가 인 비어 있는 회로판 위에 네 점 , , , 가 주어진다. 과 를 하나의 전선으로 잇고, 과 를 또 다른 전선으로 이으려고 한다.
회로판은 격자이며, 각 격자점의 좌표는 (, )로 나타낸다. 전선은 항상 격자의 수직 또는 수평 방향 단위 선분을 따라서만 놓을 수 있고, 회로판 바깥으로 나갈 수 없다.
두 전선은 서로 닿으면 안 된다. 즉, 두 전선은 어떤 격자점도 공유할 수 없고 서로 교차할 수도 없다. (두 전선이 한 칸 간격을 두고 나란히 지나가는 것은 괜찮다.)
두 전선의 길이의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 회로판의 크기 과 이 공백으로 구분되어 주어진다. ()
이어지는 네 줄에 각각 , , , 의 좌표가 순서대로 주어진다. 각 좌표는 두 정수 와 로 이루어지며, , 을 만족한다. 네 점의 위치는 모두 서로 다르다.
출력
과 , 그리고 과 를 잇는 데 필요한 두 전선의 길이의 합의 최솟값을 출력한다. 조건에 맞게 두 전선을 놓는 것이 불가능하면 IMPOSSIBLE을 출력한다.