扫描线 + 线段树 : 求矩形面积的并 ---- hnu : 12884 Area Coverage

Area Coverage
Time Limit: 10000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 16, Accepted users: 12
Problem 12884 : No special judgement
Problem description

In this day and age, a lot of the spying on other countries is done with the use of satellites and drones equipped with cameras. All these photographs of various sizes and from various sources can be combined to give a picture of the country as a whole.
Given the photographs (that is to say, the rectangular area covered by each, since the contents of the photographs themselves are of course top-secret!), can you work out what the total area is of all that is photographed? Note that certain areas can appear on multiple photographs and should be counted only once.



Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

上一篇:图论 --- spfa + 链式向前星 : 判断是否存在正权回路 poj 1860 : Currency Exchange


下一篇:计算几何 --- 凸包 模板