모눈종이 자르기

1 cm 간격의 가로선과 세로선이 그어진 직사각형 모눈종이 위에 한 개의 다각형이 그려져 있다. 다각형의 모든 변은 모눈종이의 선 위에 있다. 이 다각형의 변을 따라 오려내면 모눈종이에는 하나 이상의 조각이 남는다.

모눈종이의 가로 길이와 세로 길이, 그리고 다각형 하나가 주어진다. 다각형을 오려낸 뒤 남는 조각의 개수와, 그 조각들 중 둘레가 가장 긴 조각의 둘레 길이를 구하는 프로그램을 작성하시오.

첫 번째 그림처럼 다각형을 오려내면 세 개의 조각이 남는다. 조각 1, 조각 2, 조각 3의 둘레 길이는 각각 36 cm, 14 cm, 30 cm이므로 가장 긴 둘레는 36 cm이다.

다각형을 오려낸 뒤 남은 조각에 구멍이 있으면, 그 조각의 둘레 길이는 모눈종이의 바깥 둘레와 오려낸 다각형의 둘레를 더한 값이다. 다음 그림에서 남은 조각의 둘레 길이는 44 cm이다.

아래 그림처럼 두 꼭짓점의 위치가 같거나, 두 변이 서로 교차하거나, 두 변이 일부라도 서로 겹치면 다각형으로 보지 않는다.

모눈종이에 그려진 다각형은 임의의 꼭짓점에서 시작하여 반시계 방향으로 차례대로 주어지는 꼭짓점들의 위치로 결정된다. 각 꼭짓점의 위치는 모눈종이의 왼쪽 아래 꼭짓점에서 오른쪽으로 몇 칸, 위쪽으로 몇 칸 떨어져 있는지를 나타내는 두 수로 주어진다.

첫째 줄에는 모눈종이의 가로 길이와 세로 길이를 나타내는 자연수가 빈칸을 사이에 두고 주어진다. 두 길이는 모두 200000 이하이다.

둘째 줄에는 오려낼 다각형의 꼭짓점 개수를 나타내는 500000 이하의 자연수가 주어진다.

이어지는 줄에는 다각형의 꼭짓점 위치가 반시계 방향 순서로 한 줄에 하나씩 주어진다. 각 꼭짓점은 모눈종이의 왼쪽 아래 꼭짓점에서 오른쪽으로 몇 칸, 위쪽으로 몇 칸 떨어져 있는지를 나타내는 두 수로 주어진다.

첫째 줄에 다각형을 오려낸 뒤 남은 조각의 개수와, 그중 가장 긴 둘레의 길이를 출력한다. 길이의 단위인 cm는 출력하지 않는다.