思路:

可以把题目转化成

给你一些沿坐标轴方向的线段 让你求交点个数

然后就线段树+扫描线 搞一搞

(线段不包含断点 最后+n 这种方式 比线段包含断点+各种特判要好写得多)

//By SiriusRen
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
int n,stkx[N],stky[N],topx,topy,top,tree[N*4];long long ans;
struct Node{int x,y;}node[N];
bool cmp1(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
bool cmp2(Node a,Node b){if(a.y!=b.y)return a.y<b.y;return a.x<b.x;}
struct Movement{
int time,num,move,l,r;
Movement(int x,int y,int z){time=x,num=y,move=z;}
Movement(int x,int y,int z,int flg){time=x,l=y,r=z,move=flg;}
Movement(){}
friend bool operator<(Movement a,Movement b){
if(a.time!=b.time)return a.time<b.time;
return a.move<b.move;
}
}movement[N*3];
void insert(int l,int r,int pos,int num,int wei){
if(l==r){tree[pos]+=wei;return;}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<num)insert(mid+1,r,rson,num,wei);
else insert(l,mid,lson,num,wei);
tree[pos]=tree[lson]+tree[rson];
}
int query(int l,int r,int pos,int L,int R){
if(L>R)return 0;
if(l>=L&&r<=R){return tree[pos];}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<L)return query(mid+1,r,rson,L,R);
else if(mid>=R)return query(l,mid,lson,L,R);
else return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&node[i].x,&node[i].y),
stkx[++topx]=node[i].x,stky[++topy]=node[i].y;
sort(stkx+1,stkx+1+topx),sort(stky+1,stky+1+topy);
topx=unique(stkx+1,stkx+1+topx)-stkx-1;
topy=unique(stky+1,stky+1+topy)-stky-1;
for(int i=1;i<=n;i++)
node[i].x=lower_bound(stkx+1,stkx+1+topx,node[i].x)-stkx,
node[i].y=lower_bound(stky+1,stky+1+topy,node[i].y)-stky;
sort(node+1,node+1+n,cmp1);
for(int i=1;i<=n;i++)if(node[i].x==node[i-1].x)
movement[++top]=Movement(node[i-1].y,node[i].x,1),
movement[++top]=Movement(node[i].y,node[i].x,-1);
sort(node+1,node+1+n,cmp2);
for(int i=1;i<=n;i++)if(node[i].y==node[i-1].y)
movement[++top]=Movement(node[i].y,node[i-1].x,node[i].x,0);
sort(movement+1,movement+1+top);
for(int i=1;i<=top;i++)
if(movement[i].move)insert(1,topx,1,movement[i].num,movement[i].move);
else ans+=query(1,topx,1,movement[i].l+1,movement[i].r-1);
printf("%lld\n",ans+n);
}

最新文章

  1. NOSDK--SDK一键打包及统一接入的实现(前言)
  2. 链表原地反转Demo
  3. log4cplus 直接创建logger 对象
  4. 基于SSL协议的双向认证 - 双向认证 [3]
  5. 有助于提高你的 Web 开发技能的7个模式库
  6. Windows 下安装项目管理工具 Redmine 1.1.2
  7. nslayoutConstraint
  8. &amp;&amp;和||的那点事儿
  9. IOS的一些尺寸
  10. PHP 性能分析第二篇: Xhgui In-Depth
  11. org.hibernate.PersistentObjectException: detached entity passed to persist异常
  12. [ES6] 23. Rest Parameters &amp; Spread Parameters
  13. 数据结构算法及应用&mdash;&mdash;二叉树
  14. asp.net 一个简单的登录控制
  15. FPGA 设计流程,延迟,时间
  16. linuxlab下虚拟板与主机通信
  17. git使用步骤
  18. 关于在html中直接引入less文件遇到的小问题
  19. 如果你在it院校学习累了,你能干什么?
  20. 【HDU 5363】Key Set(和为偶数的子集个数)

热门文章

  1. (整)deepin下mysql的安装与部分错误解决办法
  2. SQL SERVER数据库状态
  3. 一个不错的学习android的网站
  4. Java入门第一季——从此投身Java??
  5. 怎么看时序图--nand flash的读操作详解 (转)
  6. ZBrush细说3D海盗角色的创建艺术
  7. 执行 cobbler get-loaders报错
  8. 取/etc/password文件最后一个单词的最后一个字符
  9. ToDoList(原生JS)了解一下
  10. node——模块化