POJ1389 给定n个整数点矩形,求面积并。

显然ans必然是整数。

记录若干个事件,每个矩形的左边的竖边记为开始,右边的竖边记为结束。

进行坐标离散化后用线段树维护每个竖的区间, 就可以快速积分了。

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std; const int maxn=100005;
struct Rectangle
{
int x1,y1,x2,y2;
}; struct Event
{
int x,y1,y2,add;
}; struct IntervalTreeNode
{
int count,total;
}; int n; Rectangle rect[maxn];
Event evt[maxn<<1];
IntervalTreeNode tree[(maxn+10)<<2];
int id[maxn<<1];
bool cmp(const Event &a,const Event &b)
{
if(a.x<b.x)return true;
return false;
} void up(int i,int lb,int rb)
{
tree[i].total=tree[i<<1].total+tree[(i<<1)+1].total;
if(tree[i].count)tree[i].total=id[rb]-id[lb];
} void ins(int i,int lb,int rb,int a,int b,int k)
{
if(a==lb&&b==rb){
tree[i].count+=k;
up(i,lb,rb);
return ;
}
int med=(lb+rb)>>1;
if(b<=med) ins(i<<1,lb,med,a,b,k);
else if(a>=med)ins((i<<1)+1,med,rb,a,b,k);
else{
ins(i<<1,lb,med,a,med,k);
ins((i<<1)+1,med,rb,med,b,k);
}
up(i,lb,rb);
} long long area()
{
for(int i=0;i<n;i++){
id[i]=rect[i].y1;
id[i+n]=rect[i].y2;
}
sort(id,id+2*n);
for(int i=0;i<2*n;i++){
rect[i].y1=lower_bound(id,id+2*n,rect[i].y1)-id;
rect[i].y2=lower_bound(id,id+2*n,rect[i].y2)-id;//坐标离散化
}
for(int i=0;i<n;i++){
evt[i].add=1;
evt[i+n].add=-1;
evt[i].x=rect[i].x1;
evt[i+n].x=rect[i].x2;
evt[i].y1=evt[i+n].y1=rect[i].y1;
evt[i].y2=evt[i+n].y2=rect[i].y2;
}
sort(evt,evt+n*2,cmp);
long long int ans=0;
for(int i=0;i<2*n;i++){
if(i>0&&evt[i].x>evt[i-1].x){
ans+=(long long )(evt[i].x-evt[i-1].x)*tree[1].total;
}
ins(1,0,2*n-1,evt[i].y1,evt[i].y2,evt[i].add);
}
return ans;
} int main()
{freopen("t.txt","r",stdin);
while(true)
{
n=0;
scanf("%d%d%d%d",&rect[0].x1,&rect[0].y1,&rect[0].x2,&rect[0].y2);
if(rect[0].x1==-1)return -1;
while(++n)
{
scanf("%d%d%d%d",&rect[n].x1,&rect[n].y1,&rect[n].x2,&rect[n].y2);
if(rect[n].x1==-1)break;
}
printf("%I64d\n",area());
}
return 0;
}

  

最新文章

  1. linux 汇编
  2. [芯片] 3、接口技术&#183;实验三&#183;可编程并行接口8255A
  3. MFC 视图、文档、框架(通讯)
  4. Eclipse配置安卓开发环境(解决SDK manager下载慢问题)
  5. Javaweb学习笔记--分层设计
  6. 戏说Java多线程
  7. ZeroMQ注意事项
  8. Ubuntu上安装mono
  9. 05 - json转成树状结构
  10. Java 位运算符和 int 类型的实现
  11. [模板]快速傅里叶变换(FFT)
  12. Java并发编程:Java线程池核心ThreadPoolExecutor的使用和原理分析
  13. BZOJ2199[Usaco2011 Jan]奶牛议会——2-SAT+tarjan缩点
  14. python模块分析之logging日志(四)
  15. 自定义注解与validation结合使用案例
  16. Sharing Code Between Silverlight and WPF
  17. web工程迁移---jboss5迁移到jboss6
  18. python--利用列表推导式快速生成xml格式数据
  19. SD卡路径问题以及如何获取SDCard 内存
  20. System.Web.UI.Page

热门文章

  1. js ajax 传送xml dom对象到服务器
  2. 【转载】分布式系列文章——Paxos算法原理与推导
  3. 2017 计蒜之道 初赛 第一场 B阿里天池的新任务(简单)
  4. matplotlib多种绘图方式
  5. 九度oj 题目1525:子串逆序打印
  6. 仪仗队(bzoj 2190)
  7. 1085 数字游戏 2003年NOIP全国联赛普及组
  8. POJ 1182_食物链
  9. 简谈Java传值传引用
  10. litepal创建数据库表失败