색종이 면적 구하기

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

요약
네 가지 방향으로 놓인 N개의 직각 이등변 삼각형이 주어질 때, 겹친 부분을 한 번만 세어 합집합의 넓이를 소수 둘째 자리까지 구한다.
난이도

보통10점 중 7점

유형
기하, 분할 정복, 구현, 정렬
정답자
아직 제출이 없습니다

문제

Bert 는 직각 이등변 삼각형 모양의 색종이를 NN 장 가지고 있다 - 편의상 색종이는 11번 부터 NN번 까지 번호가 붙어있고, ii 번째 색종이의 이등변의 길이는 D_iD\_i 이며 이등변이 만나는 꼭짓점의 좌표는 (X_i,Y_i)(X\_i, Y\_i) 이다. 또한, 각 색종이는 이등변이 xx, yy 축에 평행하게 놓여있는데, 놓여지는 방향이 4가지 있으므로 아래 구분법에 따라 O_i∈1,2,3,4O\_i \in \\{1, 2, 3, 4\\} 값을 통해 구분한다.

Bert는 NN 장의 색종이를 주어진 좌표 위에 놓았는데, 이 때 색종이들의 총 면적의 합을 구하고 싶다 - 겹쳐진 부분이 있는 경우는 중복해서 계산하지 않도록 해야한다.

예를 들어 아래 그림의 경우 N=5N = 5 장의 색종이가 평면에 놓여있는 경우를 나타낸다. 가령 2번 상각형의 경우 O_2=3O\_2 = 3 이며 D_2=2D\_2 = 2 이고 (X_2,Y_2)=(5,5)(X\_2, Y\_2) = (5, 5) 이다. 마찬가지로 3번 삼각형의 경우 O_3=1O\_3 = 1, D_3=1D\_3 = 1, (X_3,Y_3)=(5,2)(X\_3, Y\_3) = (5, 2) 임을 알 수 있다. 이 경우는 삼각형끼리 서로 겹치는 부분이 없으므로 총 면적의 합은 8.5가 된다 (큰 삼각형 각각이 2, 작은 삼각형인 3번이 0.5).

입력으로 N,O,D,X,YN, O, D, X, Y가 주어졌을 때 Bert를 도와 색종이들의 총 면적을 구해보자.

입력

입력 첫 줄에 테스트 케이스의 수 TT 가 주어진다.

각 테스트 케이스의 첫 줄에는 색종이의 수 NN 이 주어진다. 다음 각 줄에 4개의 정수가 공백으로 구분되어 주어지는데, 순서대로 각 색종이가 놓인 방향, 이등변의 길이, 그리고 꼭지점의 좌표를 나타낸다.

출력

각 테스트 케이스의 정답을 반올림하여 소숫점 둘째자리까지 출력한다 - 반드시 소숫점 이하 두 자리를 출력해야한다 (예제 참고).

제한

  • 1≤T≤101 \le T \le 10

  • 1≤N≤501 \le N \le 50

  • 1≤i≤N1 \le i \le N 인 각 ii 에 대하여

    • O_i∈1,2,3,4O\_i \in \\{1, 2, 3, 4\\}
    • 1≤D_i≤1001 \le D\_i \le 100
    • 0≤X_i,Y_i≤1000 \le X\_i, Y\_i \le 100
    • 각 삼각형의 꼭짓점을 이루는 좌표 (x,y)(x, y)에 대해서 0≤x,y≤1000 \le x, y \le 100

예제1

  1. 예제 1

    입력
    5
2
1 2 3 3
1 1 3 3
4
1 2 4 10
2 2 4 10
3 2 4 10
4 2 4 10
12
1 2 4 10
2 2 4 10
3 2 4 10
4 2 4 10
1 3 5 7
2 3 5 7
3 3 5 7
4 3 5 7
1 1 6 7
2 1 6 7
3 1 6 7
4 1 6 7
5
1 2 3 3
3 2 5 5
1 1 5 2
2 2 1 1
4 2 3 3
4
1 100 100 0
2 100 0 0
3 100 100 100
4 100 0 100
    예상 출력
    2.00
8.00
24.50
8.50
10000.00