hdu1542 Atlantis （线段树+扫描线+离散化）

hdu1542 Atlantis （线段树+扫描线+离散化）

Atlantis

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9032    Accepted Submission(s): 3873

Problem Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1

Output

For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point. Output a blank line after each test case.

Sample Input

2 10 10 20 20 15 15 25 25.5 0

Sample Output

Test case #1 Total explored area: 180.00

Source

​​Mid-Central European Regional Contest 2000​​

Recommend

linle   |   We have carefully selected several similar problems for you:   ​​1828​​​  ​​​1255​​​  ​​​1540​​​  ​​​2795​​​  ​​​1823​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

第一次做线段树+扫描线+离散化..当然是不会做的 甚至都没听说过

所以百度+查资料+看了n久 终于有了一点眉目。。

​​离散化​​是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。

在这里先按照x大小排序。（10，15，20，25）这样的话我们就知道矩形的长，然后就该求宽了。知道宽面积

不就是手到擒来嘛。至于求宽就是把y坐标离散化，然后开始建树，扫描求宽了。记得一次加入一个y坐标，其实

就是一个y=?的一条线、每添加两条线计算一次面积（如果添加1 2 3次计算两次面积求和），然后求和

这就是本题例题的四个扫描线。。第一次是标号为1的左边，第二次面积为红色，第三次为绿色，第四次就是蓝色

#include #include using namespace std;struct node1{ double x,y1,y2,flag;//flag表示该边是入边还是出边}c[205];struct node2{ double left,right,len,s;//s标记这条边是否完全覆盖 int l,r;}d[205*4];double y[205];//所有y坐标bool cmp(node1 a,node1 b){ return a.x0)非0 完全覆盖 d[root].len=d[root].right-d[root].left; else if(d[root].r-d[root].l==1) d[root].len=0; else d[root].len=d[root*2].len+d[root*2+1].len;}void update(int root,node1 x){ if(d[root].left==x.y1&&d[root].right==x.y2) { d[root].s+=x.flag; cal(root); return ; } if(x.y1>=d[root*2].right) update(root*2+1,x); else if(x.y2<=d[root*2+1].left) update(root*2,x); else { node1 temp; temp=x; temp.y2=d[root*2].right; update(root*2,temp); temp=x; temp.y1=d[root*2+1].left; update(root*2+1,temp); } cal(root); return ;}int main(){ int n,ncase=1; while(scanf("%d",&n)&&n) { int t=1; for(int i=0;i c[t].x=x2,c[t].y1=y1,c[t].y2=y2,c[t].flag=-1,y[t++]=y2;//出边 } sort(c+1,c+t,cmp); sort(y+1,y+t); build(1,1,t-1); update(1,c[1]); double sum=0; for(int i=2;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。