给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1
7.63
0.00#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct Line
{
double x1;
double x2;
double h;
int cover;
}line[100000];
struct Node
{
int left;
int right;
double once;
double more;
int cover;
}node[100000];
double xx[100000];
///////////////////////////////////////////////////////////////////////
int cmp(const void *a,const void *b)
{
return (*(struct Line *)a).h>(*(struct Line *)b).h?1:-1;//从小到大排列
}
void build(int left,int right,int nd)
{
node[nd].left=left;
node[nd].right=right;
node[nd].cover=0;
node[nd].more=0;
node[nd].once=0;
if(left==right) return ;
int mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
}
void update(int t)
{
if( node[t].cover >= 2 )
{
node[t].once = 0;
node[t].more = xx[node[t].right+1] - xx[node[t].left];
return ;
}
if( node[t].cover == 1 )
{ //覆盖一次 则覆盖两次的长度为儿子覆盖一次和两次的长度之和 覆盖一次的长度则为总长度减去覆盖多次的长度 因为不可能存在没被覆盖的区域
if( node[t].left == node[t].right )
node[t].more = 0;
else
node[t].more = node[t*2].more+ node[t*2+1].more + node[t*2].once + node[t*2+1].once;//当前节点覆盖一次 但是儿子节点之前覆盖了一次的现在又覆盖了一次 故变成了新的覆盖的2次
node[t].once = xx[node[t].right+1] -xx[node[t].left] - node[t].more;
return ;
}
if( node[t].cover == 0 )
{
if( node[t].left == node[t].right )
node[t].more = node[t].once = 0;
else
{
node[t].more = node[t*2].more + node[t*2+1].more;
node[t].once = node[t*2].once + node[t*2+1].once;
}
return ;
}
}
void insert(int left,int right,int cover,int nd)
{
if(left==node[nd].left&&right==node[nd].right)
{
node[nd].cover+=cover;
update(nd);
return ;
}
int mid=(node[nd].left+node[nd].right)/2;
if(right<=mid) insert(left,right,cover,nd*2);
else
if(left>mid) insert(left,right,cover,nd*2+1);
else
{
insert(left,mid,cover,nd*2);
insert(mid+1,right,cover,nd*2+1);
}
update(nd);
}
int bsearch(int p,int q,double c)
{
while(p<=q){
int mid=(p+q)/2;
if(xx[mid]==c)
return mid;
if(xx[mid]<c)
p=mid+1;
else
q=mid-1;
}
return -1;
}
int main()
{
int cas,n,k,i,j;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
k=0;
for(i=0;i<n;i++)
{
double x1,y1,x2,y2;
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
line[k].x1=x1;
line[k].x2=x2;
line[k].cover=1;
line[k].h=y1;
xx[k]=x1;
k++;
line[k].x1=x1;
line[k].x2=x2;
line[k].cover=-1;
line[k].h=y2;
xx[k]=x2;
k++;
}
sort(xx,xx+k);
qsort(line,k,sizeof(line[0]),cmp);
j=k;k=1;//j条边
for(i=1;i<j;i++)
{
if(xx[i]!=xx[i-1])
xx[k++]=xx[i];
}
k--;
build(0,k,1);
double ans=0;
for(i=0;i<j-1;i++)//j-1 哦
{
int left,right;
left=bsearch(0,k,line[i].x1);
right=bsearch(0,k,line[i].x2)-1;
if(right<left)//两个点重复时,特殊处理! 这里其实额也搞不懂 去掉也能过 估计是测试数据里没有这样的数据
{
ans+=(line[i+1].h-line[i].h)*node[1].more;
continue;
}
insert(left,right,line[i].cover,1);
ans+=(line[i+1].h-line[i].h)*node[1].more;
}
printf("%.2lf\n",ans);
}
return 0;
}
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
Hdu 1237 解题代码
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码