다각형 윤곽선 칠하기

각 다각형 변을 이후 다각형들과의 교점에서 나눈 뒤, 조각마다 그 조각을 포함하는 이후 다각형의 개수 t를 세어 1/(t+1)을 곱해 더한다.

어려움8기하구현완전 탐색아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

아드리안은 좌표평면에 볼록다각형을 수채 물감으로 그린다. 시간이 모자라 내부는 칠하지 않지만 그린 순서만은 드러내고 싶어서, 다각형 경계 위의 각 점을 그 점을 덮는 다각형의 개수에 따라 다른 농도로 그린다. 아드리안이 다각형 p1,p2,,pnp_1, p_2, \dots, p_n 을 이 순서로 그린다고 하자. 다각형 pjp_j 의 어떤 선분이 양 끝점을 뺀 나머지 부분에서 나중에 그리는 다각형 pj+1,,pnp_{j+1}, \dots, p_n 중 정확히 tt 개의 내부에 놓이면, 아드리안은 그 선분을 농도 tt 로 그린다.

농도 tt 로 선분을 그릴 때는 길이 11 마다 검은 물감을 1t+1\frac{1}{t+1} 단위씩 쓴다. 모든 다각형을 그리는 데 필요한 물감의 총량을 구하라.

입력

첫 줄에 다각형의 개수 nn (1n101 \le n \le 10) 이 주어진다. 이어서 nn 개의 블록이 주어지고, kk 번째 블록은 다각형 pkp_k 를 설명한다. 각 블록의 첫 줄에는 꼭짓점의 개수 mm (3m203 \le m \le 20) 이 주어지고, 다음 mm 개의 줄에는 꼭짓점 하나의 좌표를 나타내는 두 정수 xxyy (0x,y1000 \le x, y \le 100) 가 주어진다. 꼭짓점은 반시계 방향으로 주어지며, 다각형은 항상 볼록하고 연속한 두 변이 평행한 경우는 없다.

서로 다른 두 다각형은 꼭짓점이나 변에서 닿지 않는다. 정확히 말하면 AABB 가 서로 다른 다각형 pip_ipjp_j 의 변일 때, 둘은 공통점이 하나도 없거나 AA 의 내부이면서 BB 의 내부이기도 한 한 점에서만 만난다.

출력

필요한 물감의 총량을 소수점 아래 여섯 자리로 반올림해 한 줄에 출력한다.

힌트

첫 번째 예제의 그림이다.

첫 번째 예제

두 번째 예제의 그림이다.

두 번째 예제