아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

다각형 윤곽선 칠하기

시간 제한1초메모리 제한512 MB

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

어려움10점 중 8점

유형
기하, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

아드리안은 좌표평면에 볼록다각형을 수채 물감으로 그린다. 시간이 모자라 내부는 칠하지 않지만 그린 순서만은 드러내고 싶어서, 다각형 경계 위의 각 점을 그 점을 덮는 다각형의 개수에 따라 다른 농도로 그린다. 아드리안이 다각형 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 (1≤n≤101 \le n \le 10) 이 주어진다. 이어서 nn 개의 블록이 주어지고, kk 번째 블록은 다각형 pkp_k 를 설명한다. 각 블록의 첫 줄에는 꼭짓점의 개수 mm (3≤m≤203 \le m \le 20) 이 주어지고, 다음 mm 개의 줄에는 꼭짓점 하나의 좌표를 나타내는 두 정수 xx 와 yy (0≤x,y≤1000 \le x, y \le 100) 가 주어진다. 꼭짓점은 반시계 방향으로 주어지며, 다각형은 항상 볼록하고 연속한 두 변이 평행한 경우는 없다.

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

출력

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

힌트

첫 번째 예제의 그림이다.

첫 번째 예제

두 번째 예제의 그림이다.

두 번째 예제

예제2

  1. 예제 1

    입력
    2
    3
    2 10
    5 1
    10 10
    3
    1 2
    9 2
    6 12
    
    예상 출력
    51.981331
    
  2. 예제 2

    입력
    3
    5
    1 1
    10 1
    11 5
    7 8
    1 5
    3
    2 2
    9 2
    5 9
    4
    1 8
    9 0
    10 3
    10 7
    
    예상 출력
    69.859255