빙산

Tania는 해양 생물학자다. 그녀의 목표는 기후 변화가 마카로니 펭귄 개체수에 미치는 영향을 측정하는 것이다. 대부분의 펭귄 종처럼 마카로니 펭귄은 남반구, 남극 근처에 산다. Tania는 주로 "Îles Nuageuses"(영어로 "Cloudy Islands") 근처의 마카로니 펭귄 개체수에 관심이 있다.

여름에는 섬 주변의 얼음이 녹아 섬이 모든 새를 수용하기에 너무 작아진다. 일부 펭귄은 주변에 떠 있는 빙산에 산다. 연구를 위해 Tania는 그 빙산의 넓이를 측정해야 한다.

위성 영상과 이미지 인식을 이용해 Tania는 빙산 지도를 얻었다. 당신의 목표는 빙산의 넓이를 측정하는 것이다. Tania가 연구하는 섬은 꽤 작아서 지구를 국소적으로 평평한 표면으로 근사할 수 있다. 따라서 Tania의 지도는 일반적인 2차원 직교 좌표계를 사용하고, 넓이도 일반적인 방식으로 계산한다. 예를 들어 방정식 x1 ≤ x ≤ x2와 y1 ≤ y ≤ y2로 정의되는, 축에 평행한 직사각형의 넓이는 (x2 − x1) × (y2 − y1)이다.

Tania의 표현에서 빙산은 경계로 표현되는 다각형이다. Tania는 각 빙산에 대해 빙산의 경계를 정의하는 점의 수열 p1, . . . , pk를 기록했다. 여러 빙산은 서로 닿지 않고 겹치지도 않는다. 또한 빙산의 경계 p1, . . . , pk는 항상 "단순" 다각형이다. 즉 [p1; p2], . . . , [pk; p1] 중 어느 두 선분도 서로 교차하지 않는다.

입력은 다음 줄들로 이루어진다.

• 첫째 줄에 다각형의 수를 나타내는 정수 N이 주어진다.

• 이어서 N개의 줄 묶음이 주어지며, 각 묶음은 하나의 다각형을 나타내고 다음으로 구성된다.

  • 첫째 줄에 다각형의 경계를 정의하는 점의 수 P,
  • 다음 P개 줄에 각 경계 점의 좌표를 나타내는 두 정수 x와 y가 공백으로 구분되어 주어진다.

출력은 총 넓이를 가장 가까운 정수 아래로 반올림한 하나의 정수여야 한다. 다시 말해, 출력은 입력에 주어진 다각형들의 총 넓이 A가 I 이상 I + 1 미만(I ≤ A < I + 1)이 되게 하는 하나의 정수 I를 한 줄에 담아야 한다.

다각형의 수 N은 1 ≤ N ≤ 1 000이다.

• 각 다각형은 3 ≤ P ≤ 50인 P개의 점으로 정의된다.
• 모든 좌표는 0 ≤ x, y ≤ 106이다.