모눈종이 자르기 timer 1초 memory 128MB

1㎝ 간격으로 가로선과 세로선이 그어진 직사각형 모양의 모눈종이 위에 한 개의 다각형이 그려져 있다. 

다각형의 모든 변은 모눈종이에 그어진 선 위에 있다.

다각형의 변을 따라 모눈종이에서 다각형을 오려내고 나면 하나 이상의 조각들이 남는다.

모눈종이의 가로 길이, 세로 길이와 다각형 한 개가 주어질 때,

이 다각형을 오려낸 후 남은 조각들의 개수와 둘레가 가장 긴 조각의 둘레 길이를 출력하는 프로그램을 작성하시오.

예를 들어, 다음 그림과 같이 모눈종이에 그려진 다각형을 오려내면, 세 개의 조각이 만들어 진다. 

조각 1, 조각 2, 조각 3의 둘레 길이는 각각 36㎝, 14㎝, 30㎝이므로, 가장 둘레가 긴 조각의 둘레 길이는 36㎝이다.

모눈종이에서 다각형을 오려낸 후 남은 조각에 구멍이 있는 경우,

이 조각의 둘레 길이는 모눈종이의 둘레 길이와 다각형의 둘레 길이의 합이다. 

예를 들어, 다음 그림에서 조각의 둘레의 길이는 44㎝이다.

단, 아래 그림과 같이 두 꼭지점의 위치가 같거나 두 변이 서로 교차하는 경우, 

두 변이 일부라도 서로 겹치는 경우는 모두 다각형이 아니다.

모눈종이에 그려진 다각형은 임의의 꼭지점부터 시작하여 시계반대방향으로 차례로 주어진 꼭지점들의 위치에 의하여 결정된다. 

다각형의 각 꼭지점의 위치는 

모눈종이의 왼쪽 아래 꼭지점으로부터 오른쪽으로 몇 칸, 위쪽으로 몇 칸 떨어져 있는 지를 나타내는 두 수로 주어진다. 

부분 점수는 없다.