| 색 유리창 |
|---|
N개의 사각형 회색 유리창을 겹쳐서 스테인드글라스를 만들려고 한다. 각각의 유리창에는 고유의 ‘착색도’라는 정수값이 부여되어 있는데, 2개의 유리창이 겹치면 두 유리창의 착색도 합이 겹친 부분의 착색도가 된다. 유리창은 x-축과 y-축에 평행하게 놓여지며, 각 유리창의 위치값을 모두 알고 있다고 가정한다. 이런 방식으로 스테인드글라스를 완성했을 때 착색도가 T 이상인 영역의 넓이를 구하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
첫 번째 줄에는 유리창의 개수인 정수 N(1<=N<=1000)이 주어진다. 두 번째 줄에는 착색도의 최대값인 T(1<=T<=1,000,000,000)이 주어진다. 그 다음으로 N개의 줄에 걸쳐 유리창에 대한 정보가 주어진다. 유리창에 대한 정보는 5개의 정수 xl, yt, xr, yb, ti 이며, (xl, yt)은 왼쪽 상단의 꼭지점 좌표이고, (xr, yb)은 오른쪽 하단의 꼭지점 좌표이고, ti는 착색도를 의미한다. 입력값의 범위는 1<=ti<=1,000,000, 0<=<xl<xr<=K, 0<yt<yb<=K 이며, 테스트 케이스의 10%는 N<=100, K<=100 이고, | |
| 출력 | |
|---|---|
완성된 스테인드글라스에서 착색도가 T 이상인 영역의 면적을 출력한다. 면적의 크기는 264를 초과하지 않으며, 일부의 경우는 232 이상이다. ※ 예시 1 : | |
4개의 유리창이 오른쪽 그림처럼 겹쳐있으며, 착색도가 3 이상인 영역이 2개다. 첫번째 영역은 (13,11)과 (14,15) 이고, 두 번째 영역은 (17,12)와 (18,13) 이다. 이 두 영역의 면적의 합은 5다.| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 4 3 11 11 20 15 1 13 8 14 17 2 17 8 18 17 1 12 12 19 13 1 | |
| 출력 | 5 | ||