暴力枚举+扫描线+线段树——cf1194E
2024-10-07 19:46:25
/*
思路就是枚举矩形下面那条先,把所有和其交叉的竖线更新进线段树,然后扫描先向上更新,遇到竖线上端点就在线段树里删掉,遇到横线就更新答案
*/
#include<bits/stdc++.h>
using namespace std;
#define N 20005
#define ll long long struct SegV{int x,y1,y2;}v[N];//垂直线
struct SegH{int y,x1,x2;}h[N];//水平线
int cmp(SegH a,SegH b){return a.y<b.y;} int n,cntv,cnth;
int y[N],cnty,x[N],cntx;
vector<SegV>Up[N],Down[N]; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[N<<];
void update(int pos,int v,int l,int r,int rt){
if(l==r){sum[rt]+=v;return;}
int m=l+r>>;
if(pos<=m)update(pos,v,lson);
else update(pos,v,rson);
sum[rt]=sum[rt<<]+sum[rt<<|];
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return sum[rt];
int m=l+r>>,res=;
if(L<=m)res+=query(L,R,lson);
if(R>m)res+=query(L,R,rson);
return res;
}
int main(){
cin>>n;
for(int i=;i<=n;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
x[++cntx]=x1;x[++cntx]=x2;
y[++cnty]=y1;y[++cnty]=y2;
if(x1==x2){//垂直线
cntv++;
v[cntv].x=x1;
v[cntv].y1=min(y1,y2);
v[cntv].y2=max(y1,y2);
}
else {
cnth++;
h[cnth].y=y1;
h[cnth].x1=min(x1,x2);
h[cnth].x2=max(x1,x2);
}
} sort(x+,x++cntx);
cntx=unique(x+,x++cntx)-x-;
sort(y+,y++cnty);
cnty=unique(y+,y++cnty)-y-; for(int i=;i<=cnth;i++){
h[i].y=lower_bound(y+,y++cnty,h[i].y)-y;
h[i].x1=lower_bound(x+,x++cntx,h[i].x1)-x;
h[i].x2=lower_bound(x+,x++cntx,h[i].x2)-x;
}
for(int i=;i<=cntv;i++){
v[i].x=lower_bound(x+,x++cntx,v[i].x)-x;
v[i].y1=lower_bound(y+,y++cnty,v[i].y1)-y;
v[i].y2=lower_bound(y+,y++cnty,v[i].y2)-y;
} sort(h+,h++cnth,cmp);//给水平线从低到高排序
for(int i=;i<=cntv;i++){//按端点处理垂直线
Up[v[i].y2].push_back(v[i]);
Down[v[i].y1].push_back(v[i]);
} long long ans=;
for(int i=;i<=cnth;i++){
memset(sum,,sizeof sum);
//把所有和h[i]交叉的竖线更新进线段树
for(int j=;j<=cntv;j++)
if(v[j].y1<=h[i].y && v[j].y2>=h[i].y)
update(v[j].x,,,cntx,);
//开始向上枚举所有水平线
int now=h[i].y;//当前的高度
for(int j=i+;j<=cnth;j++)if(h[i].y!=h[j].y){
while(now+<=h[j].y){
++now;
for(auto v:Up[now-]){//把这个高度以下的都删掉
if(v.y1<=h[i].y)
update(v.x,-,,cntx,);
}
}
int L=max(h[i].x1,h[j].x1),R=min(h[i].x2,h[j].x2);
if(L<=R){
int res=query(L,R,,cntx,);
ans+=res*(res-)/;
}
}
}
cout<<ans<<endl;
}
最新文章
- iOS开发小技巧 - label中的文字添加点击事件
- Can&#39;t load IA 32-bit .dll on a AMD 64-bit platform错误的解决
- MongoDB学习笔记~Update方法更新集合属性后的怪问题
- (原创)详解Quartus导出网表文件:.qxp和.vqm
- 如何从oc中去获取一个私有的变量.....
- String类的基本用法与注意点,StringBuffer类的用法
- IIS配置不正确可能导致“远程服务器返回错误: (404) 未找到";错误一例。
- IntraWeb.v14.0.32安装及破解指南
- 怎样在thinkphp里面执行原生的sql语句
- Cortex-M3知识点
- windows7 64位下运行 regsvr32 注册ocx或者dll的方法
- hdu1104 Remainder bfs找算式是否有解……
- poj 1220 NUMBER BASE CONVERSION(短除法进制转换)
- 基于.NET的微信SDK
- IIS:错误: 无法提交配置更改,因为文件已在磁盘上更改
- Dynamics CRM2016 Web Api之时间字段值的处理
- birt4.6部署到tomcat及启动服务报错解决方法
- Python turtle绘制阴阳太极图代码解析
- 082 HBase的几种调优(GC策略,flush,compact,split)
- linux 磁盘空间满了,排查记录