参考博客:

http://blog.csdn.net/xingyeyongheng/article/details/8927732

总的来说就是用一条(假想的)线段去平行x轴从下往上扫描,扫描的过程中更新下底边的个数和长度综合(用线段树维护)

因为x的值可能会很大,所以就要用Hash表来进行离散化,排序,去重,查找的时候直接二分就好了

二分搜索传参数的时候double写成了int交上去居然是mle(想不通为什么)

注释都在代码里面了

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; int mark[N<<];//某区间下底边个数
double sum[N<<];//某区间下底边总长度
double Hash[N];//离散化数组
//把横坐标作为线段进行扫描
//扫描是为了更新下底边个数和下底边总长度,记录答案
struct tree{
double l,r,h;//l,r左右端点,h从x轴到该边的高
int d;//-1上底边/1下底边
tree(){}
tree(double x,double y,double z,int a):l(x),r(y),h(z),d(a){}
bool operator <(const tree &a)const
{
return h<a.h;
}
}s[N];
void pushup(int l,int r,int rt)
{
if(mark[rt])sum[rt]=Hash[r+]-Hash[l];
else if(l==r)sum[rt]=;
else sum[rt]=sum[rt<<]+sum[rt<<|];
}
void update(int L,int R,int d,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
mark[rt]+=d;//如果是上底边mark-1,下底边mark+1
pushup(l,r,rt);
return ;
}
int m=(l+r)>>;
if(L<=m)update(L,R,d,ls);
if(R>m)update(L,R,d,rs);
pushup(l,r,rt);
}
int Search(double key,int n)
{
int l=,r=n-;
while(l<=r)
{
int m=(l+r)/;
if(Hash[m]==key)return m;
if(Hash[m]>key)r=m-;
else l=m+;
}
return -;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout<<setiosflags(ios::fixed)<<setprecision();
int n,cnt=;
while(cin>>n,n)
{
int k=;
for(int i=;i<n;i++)
{
double x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
Hash[k]=x1;
s[k++]={x1,x2,y1,};//上底边
Hash[k]=x2;
s[k++]={x1,x2,y2,-};//下底边
}
sort(Hash,Hash+k);
sort(s,s+k);
int m=;
for(int i=;i<k;i++)//离散化
if(Hash[i]!=Hash[i-])
Hash[m++]=Hash[i];
double ans=;
memset(sum,,sizeof sum);
memset(mark,,sizeof mark);
for(int i=;i<k;i++)//如果两个下底边重合,但是上底边可能不一样,必须更新mark,而sum不会改变
{
int l=Search(s[i].l,m);//利用hash表查找
int r=Search(s[i].r,m)-;//这里的l,r实际上是Hash表的标号
update(l,r,s[i].d,,m-,);//维护mark和sum的值
ans+=sum[]*(s[i+].h-s[i].h);//sum[1]当前的下底边长度总和
}
cout<<"Test case #"<<++cnt<<endl;
cout<<"Total explored area: "<<ans<<endl<<endl;
}
return ;
}
/********************* *********************/

最新文章

  1. css3制作旋转动画
  2. 7.3 数据注解特性之ConcurrencyCheck特性【Code-First系列】
  3. SwitchHosts—hosts管理利器
  4. winRT Com组件开发流程总结
  5. eclipse构建及运行maven web项目
  6. eclipse 中的 jar file 和 runnable jar file的区别
  7. C++ 类的静态成员详细讲解[转]
  8. HW3.26
  9. 1021 Fibonacci Again (hdoj)
  10. NET 项目结构搭建
  11. js根据条件json生成随机json:randomjson
  12. mysql更新某个字符串字段的部分内容
  13. python默认编码设置
  14. Vue脚手架搭建项目
  15. npm ERR! code ENOENT
  16. 使用C# (.NET Core) 实现迭代器设计模式 (Iterator Pattern)
  17. Docker操作删除所有容器镜像
  18. 常见排序的JAVA实现和性能测试
  19. Spark分析之BlockManager
  20. Cookie的创建与删除

热门文章

  1. Vue父组件调用子组件的方法
  2. Python3.6全栈开发实例[014]
  3. leetcode第一刷_Rotate Image
  4. Vuex核心知识(转)
  5. More about Parameter Passing in Python(Mainly about list)
  6. c# 执行批处理文件
  7. 每天一个Linux命令(48)ping命令
  8. imx6q Xorg下Qt应用开机自启动及添加桌面快捷启动图标的方法
  9. Xamarin简介与Xamarin支持MVC设计模式
  10. 跨平台移动开发 手机上使用Iscroll.Js的Banner