1㎝ 간격으로 가로선과 세로선이 그어진 직사각형 모양의 모눈종이 위에 한 개의 다각형이 그려져 있다. 다각형의 모든 변은 모눈종이에 그어진 선 위에 있다. 다각형의 변을 따라 모눈종이에서 다각형을 오려내고 나면 하나 이상의 조각들이 남는다.
모눈종이의 가로 길이, 세로 길이와 다각형 한 개가 주어질 때, 이 다각형을 오려낸 후 남은 조각들의 개수와 둘레가 가장 긴 조각의 둘레 길이를 출력하는 프로그램을 작성하시오.
예를 들어, 다음 그림과 같이 모눈종이에 그려진 다각형을 오려내면, 세 개의 조각이 만들어 진다. 조각 1, 조각 2, 조각 3의 둘레 길이는 각각 36㎝, 14㎝, 30㎝이므로, 가장 둘레가 긴 조각의 둘레 길이는 36㎝이다.
모눈종이에서 다각형을 오려낸 후 남은 조각에 구멍이 있는 경우, 이 조각의 둘레 길이는 모눈종이의 둘레 길이와 다각형의 둘레 길이의 합이다. 예를 들어, 다음 그림에서 조각의 둘레의 길이는 44㎝이다.
단, 아래 그림과 같이 두 꼭지점의 위치가 같거나 두 변이 서로 교차하는 경우, 두 변이 일부라도 서로 겹치는 경우는 모두 다각형이 아니다.
모눈종이에 그려진 다각형은 임의의 꼭지점부터 시작하여 시계반대방향으로 차례로 주어진 꼭지점들의 위치에 의하여 결정된다. 다각형의 각 꼭지점의 위치는 모눈종이의 왼쪽 아래 꼭지점으로부터 오른쪽으로 몇 칸, 위쪽으로 몇 칸 떨어져 있는 지를 나타내는 두 수로 주어진다.
실행시간은 0.5초를 넘을 수 없다. 부분 점수는 없다.
입력 10 12 14 9 6 5 6 5 8 10 8 10 10 1 10 1 4 0 4 0 2 5 2 5 0 7 0 7 3 9 3 출력 3 36 입력 8 7 6 1 3 1 2 5 2 5 5 3 5 3 3 출력 1 44
출처: koi 2007 년 본선 초등 2 번