可以转变成上一题(hdu1542)的形式,把每条线段变成宽为1的矩形,求矩形面积并

要注意的就是转化为右下角的点需要x+1,y-1,画一条线就能看出来了

#include<bits/stdc++.h>
#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<<];//某区间下底边个数
ll sum[N<<];//某区间下底边总长度
ll Hash[N];//离散化数组
//把横坐标作为线段进行扫描
//扫描是为了更新下底边个数和下底边总长度,记录答案
struct tree{
ll l,r,h;//l,r左右端点,h从x轴到该边的高
int d;//-1上底边/1下底边
tree(){}
tree(ll x,ll y,ll 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(ll 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;
cin>>n;
int k=;
for(int i=; i<n; i++)
{
ll x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
if(x1==x2)
{
if(y1<y2)swap(y1,y2);
x2++;
y2--;
}
else
{
if(x1>x2)swap(x1,x2);
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];
ll 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<<ans<<endl;
return ;
}
/********************* *********************/

最新文章

  1. code
  2. java多线程系类:JUC线程池:01之线程池架构
  3. java.sql.SQLException: ORA-00972: 标识符过长
  4. Java日志系统框架的设计与实现
  5. jquery事件之event.target用法详解
  6. 关于oracle dbms_job 定时执行的内容。
  7. Lazy&lt;T&gt;在Entity Framework中的性能优化实践
  8. 配置Server Side TAF
  9. 2D图形如何运动模拟出3D效果
  10. swagger坑
  11. 观察者模式--java
  12. js--sort()排序方法的使用--(笔记)
  13. 详细解说Tomcat 设置虚拟路径的几种方法及为什么设置虚拟路径
  14. jquery.form.js mvc 上传文件 layer 选择框与等待效果
  15. 20162326 Exp1《网络对抗技术》 PC平台逆向破解
  16. Golang作用域—坑
  17. JavaScript匿名类整理学习笔记
  18. Yii 1.1.17 六、开启路由与使用缓存
  19. facebook注册不了无法打开官网的解决办法
  20. warning no newline at the end of file

热门文章

  1. 2014-08-28——移动端,触摸事件 touchstart、touchmove、touchend、touchcancel
  2. 父标签浮动(float)“塌陷”问题
  3. 目标是:互联网方向的Java开发工程师
  4. 非Linux环境下调用sh命令
  5. HDFS权限
  6. hive查询表,返回结果是null
  7. 【LeetCode】【定制版排序】Sort Colors
  8. [转]AOP那些学术概念—通知、增强处理连接点(JoinPoint)切面(Aspect)
  9. 基于SSM的单点登陆01
  10. SQL查询语句的执行顺序