2017-09-24 20:11:21

writer:pprp

找到的大神的代码,直接过了

采用了扫描线+线段树的算法,先码了,作为模板也不错啊

题目链接:https://nanti.jisuanke.com/t/17313

题意:给你很多个矩形,让你得到矩形的面积,重叠部分只算一次

代码如下:

//ac F
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm> using namespace std;
typedef long long ll;
const int maxn=1e6+; #define mm(a) memset(a,0,sizeof(a)) int num1[maxn*];
int num[maxn*],X[maxn*];
struct edge
{
int l,r,h;
int s;//s为1是下边,s为-1是上边
edge() {};
edge(int a,int b,int c,int d) : l(a),r(b),h(c),s(d) {}
bool operator<(const edge &n)const
{
return h<n.h;
}
} ss[maxn]; void pushup(int le,int ri,int node)
{
if(num1[node])
num[node]=X[ri+]-X[le];//在更新的时候,可能两个矩阵有重叠,这样就不能像以前那么更新,而是将le和ri传入
else if(le==ri)
num[node]=; //然后将X[ri+1]-X[le]的值进行更新,避免了重复的长度
else
num[node]=num[node<<]+num[node<<|];
}
void update(int l,int r,int add,int le,int ri,int node)
{
if(l<=le&&ri<=r)
{
num1[node]+=add;//与懒惰标记类似
pushup(le,ri,node);
return ;
}
int t=(le+ri)>>;
if(l<=t) update(l,r,add,le,t,node<<);
if(r>t) update(l,r,add,t+,ri,node<<|);
pushup(le,ri,node);
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
if(n == )
{
cout << "*" << endl;
break;
}
int a,b,c,d;
int k=;
for(int i=; i<n; i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
X[k]=a;
ss[k++]=edge(a,c,b,);
X[k]=c;
ss[k++]=edge(a,c,d,-);
}
sort(X,X+k);
sort(ss,ss+k);
int k1=;
for(int i=; i<k; i++) //对X进行离散化
{
if(X[i]!=X[i-]) X[k1++]=X[i];
}
mm(num);
mm(num1);
int ans=;
for(int i=; i<k-; i++)
{
int l=lower_bound(X,X+k1,ss[i].l)-X;
int r=lower_bound(X,X+k1,ss[i].r)-X-;
update(l,r,ss[i].s,,k1-,);
ans+=num[]*(ss[i+].h-ss[i].h);//num[1]为当前横坐标的总长度
}
cout << ans << endl;
}
return ;
}

最新文章

  1. 使用HEXO快速建站
  2. Learning Spark 第四章——键值对处理
  3. [转载]jquery版小型婚礼(可动态添加祝福语)
  4. Delphi多线程编程--线程同步的方法(事件、互斥、信号、计时器)简介
  5. 【原创】Django-ORM基础
  6. 10月16日下午MySQL数据库CRUD操作(增加、删除、修改、查询)
  7. 【web必知必会】—— 图解HTTP(转)good
  8. OpenCV使用边缘提取、腐蚀、轮廓进行车牌定位
  9. Azure Messaging-ServiceBus Messaging消息队列技术系列7-消息事务
  10. ListView实现下拉刷新和上拉加载功能
  11. 【数学基础篇】---详解极限与微分学与Jensen 不等式
  12. Excel的读取和保存(POI)
  13. JS 获取某个容器控件中id包含制定字符串的控件id列表
  14. 进程间通信(队列、管道)、消费者模型和进程池(apply,apply_async,map)
  15. django模型系统一
  16. TypeScript type 类型别名
  17. (转)EF5+SQLserver2012迁移到EF6+mysql5.5.47
  18. Go语言常量
  19. JS判断是否是数组的四种做法
  20. ssh-keygen生成git ssh密钥

热门文章

  1. 随笔 javascript-抽象工厂模式
  2. [报错]Unable to simultaneously satisfy constraints
  3. SecureCRT图形界面
  4. leadecode 2 Add Two Numbers
  5. python常见模块之time模块
  6. Sping-Spring JDBC框架
  7. 微信对接HIS——微信可查检验结果
  8. Spark2.0机器学习系列之11: 聚类(幂迭代聚类, power iteration clustering, PIC)
  9. C的指针疑惑:C和指针13(高级指针话题)
  10. SDUT3141:Count(哈希)好题