/*
思路就是枚举矩形下面那条先,把所有和其交叉的竖线更新进线段树,然后扫描先向上更新,遇到竖线上端点就在线段树里删掉,遇到横线就更新答案
*/
#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;
}

最新文章

  1. iOS开发小技巧 - label中的文字添加点击事件
  2. Can&#39;t load IA 32-bit .dll on a AMD 64-bit platform错误的解决
  3. MongoDB学习笔记~Update方法更新集合属性后的怪问题
  4. (原创)详解Quartus导出网表文件:.qxp和.vqm
  5. 如何从oc中去获取一个私有的变量.....
  6. String类的基本用法与注意点,StringBuffer类的用法
  7. IIS配置不正确可能导致“远程服务器返回错误: (404) 未找到&quot;错误一例。
  8. IntraWeb.v14.0.32安装及破解指南
  9. 怎样在thinkphp里面执行原生的sql语句
  10. Cortex-M3知识点
  11. windows7 64位下运行 regsvr32 注册ocx或者dll的方法
  12. hdu1104 Remainder bfs找算式是否有解……
  13. poj 1220 NUMBER BASE CONVERSION(短除法进制转换)
  14. 基于.NET的微信SDK
  15. IIS:错误: 无法提交配置更改,因为文件已在磁盘上更改
  16. Dynamics CRM2016 Web Api之时间字段值的处理
  17. birt4.6部署到tomcat及启动服务报错解决方法
  18. Python turtle绘制阴阳太极图代码解析
  19. 082 HBase的几种调优(GC策略,flush,compact,split)
  20. linux 磁盘空间满了,排查记录

热门文章

  1. Anaconda 安装 pytorch报错解决方法
  2. python字符串的截取,查找
  3. DMA实验总结
  4. 【Flutter学习】之动画实现原理浅析(三)
  5. 【dart学习】-- Dart之异步编程
  6. Android 模糊搜索rawquery bind or column index out of range: handle 0x2fb180 报错
  7. 【HDOJ6581】Vacation(模拟)
  8. \pset 、\x命令
  9. 尚学linux课程---11、vim操作命令1
  10. Hive 时间操作函数(转)