Atlantis
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9032 Accepted Submission(s): 3873
total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.
(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.
2
10 10 20 20
15 15 25 25.5
0
Test case #1
Total explored area: 180.00
pid=1255" target="_blank" style="color:rgb(26,92,200); text-decoration:none">1255
1540 2795 1823pid=1542" style="color:rgb(26,92,200); text-decoration:none">Statistic pid=1542" style="color:rgb(26,92,200); text-decoration:none">Submit pid=1542" style="color:rgb(26,92,200); text-decoration:none">Note
第一次做线段树+扫描线+离散化..当然是不会做的 甚至都没听说过
所以百度+查资料+看了n久 最终有了一点眉目。。
离散化是程序设计中一个很经常使用的技巧，它能够有效的减少时间复杂度。
其基本思想就是在众多可能的情况中“仅仅考虑我须要用的值”。离散化能够改进一个低效的算法，甚至实现根本不可能实现的算法。
要掌握这个思想。必须从大量的题目中理解此方法的特点。
在这里先依照x大小排序。
（10，15，20。25）这种话我们就知道矩形的长，然后就该求宽了。知道宽面积
不就是手到擒来嘛。至于求宽就是把y坐标离散化，然后開始建树。扫描求宽了。
记得一次增加一个y坐标，事实上
就是一个y=?的一条线、每加入两条线计算一次面积（假设加入1 2 3次计算两次面积求和），然后求和
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
这就是本题例题的四个扫描线。。第一次是标号为1的左边。第二次面积为红色，第三次为绿色。第四次就是蓝色
#include <stdio.h>
#include <algorithm>
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.x<b.x;
}
void build(int root,int l,int r)
{
d[root].l=l;
d[root].r=r;
d[root].left=y[l];
d[root].right=y[r];
d[root].len=0;
d[root].s=0;
if(l+1==r)
return ;
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid,r);//不是mid+1,比方仅仅有（10，15，20三个y坐标，应该出现三个范围（10 20）（10 15）（15 20））而不是（10 20）（10 15）
}
void cal(int root)
{
if(d[root].s>0)非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<n;i++)
{
double x1,y1,x2,y2;
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
c[t].x=x1,c[t].y1=y1,c[t].y2=y2,c[t].flag=1,y[t++]=y1;//入边<span style="white-space:pre"> </span>
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<t;i++)
{
sum+=(c[i].x-c[i-1].x)*d[1].len;
update(1,c[i]);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",ncase++,sum);
}
return 0;
}