CGL_6_A(线段树+平面扫描+离散化)
Segment Intersections: Manhattan Geometry
For given nn segments which are parallel to X-axis or Y-axis, find the number of intersections of them.
Input
In the first line, the number of segments nn is given. In the following nn lines, the ii-th segment is given by coordinates of its end points in the following format:
x1y1x2y2x1y1x2y2
The coordinates are given in integers.
Output
Print the number of intersections in a line.
Constraints
- 1≤n≤100,0001≤n≤100,000
- −1,000,000,000≤x1,y1,x2,y2≤1,000,000,000−1,000,000,000≤x1,y1,x2,y2≤1,000,000,000
- Two parallel segments never overlap or touch.
- The number of intersections ≤1,000,000≤1,000,000
Sample Input 1
6 2 2 2 5 1 3 5 3 4 1 4 4 5 2 7 2 6 1 6 3 6 5 6 7
Sample Output 1
3
题意:给你n条线段求其交点个数
题解:
22
1 1 1 2
1 2 2 2
3 2 4 2
4 2 4 3
5 1 5 2
5 2 6 2
7 2 7 3
8 2 7 2
1 4 1 6
2 4 2 6
3 4 3 6
1 6 3 6
1 5 3 5
1 4 3 4
5 4 7 4
6 4 6 5
8 4 10 4
9 4 9 3
5 5 5 7
5 6 6 6
7 6 8 6
8 5 8 7
输出:17
由上图可知一共有17个交点,我们可以进行平面扫描从平行x轴方向开始,将平行于y轴的线段分为上下两个端点然后将端点当做线段存入,然后将坐标按y进行排序对于y相同的我们可以先排平行y轴的线段的下端点,再排平行x轴的然后在排上端点。这里我们可以有一个c值来描述1为下端点2为平行于x轴的线3为上端点。
线段树我们维护x轴那段区域存在平行于y轴的数量遇到下端点就加1上端点就减1 与到平行于x轴的线段就在这段区域里面查找就对了 结合这个思想然后看图很容易理解的
巨坑的是的点可能是无序给出所以在存入的时候先排序下点 在这wa了几次
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define clr(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define il inline
#define reg register
typedef long long ll;
typedef double db;
const int maxn=10000;
const int minn=200000+5;
struct Point
{
db x,y;
Point(){}
Point(db x,db y):x(x),y(y){}
};
struct Seg
{
Point a,b;
int c;
Seg(Point a,Point b,int c):a(a),b(b),c(c){}
friend bool operator<(Seg p,Seg q){
if(p.a.y!=q.a.y) return p.a.y<q.a.y;
return p.c!=q.c?p.c<q.c:p.a.x<q.a.x;
}
};
db x[minn<<2];
int q,lenx,ans,tree[minn<<2];
vector<Seg> ve;
void init()
{
clr(tree,0);
ve.clear();
lenx=0;
ans=0;
return ;
}
void pushpu(int k,int c)
{
while(k)
{
tree[k]+=c;
k>>=1;
}
}
void update(int l,int r,int nu,int c,int k)
{
if(nu==l&&r==nu)
{
pushpu(k,c);
return ;
}
int mind=(l+r)/2;
if(nu<=mind){update(l,mind,nu,c,k<<1);}
if(nu>mind) {update(mind+1,r,nu,c,k<<1|1);}
return ;
}
void query(int l,int r,int L,int R,int k)
{
if(L<=l&&r<=R)
{
ans+=tree[k];
return ;
}
int mind=(l+r)/2;
if(L<=mind){query(l,mind,L,R,k<<1);}
if(R>mind) {query(mind+1,r,L,R,k<<1|1);}
return ;
}
int slove()
{
sort(ve.begin(),ve.end());
sort(x,x+lenx);
int res=0;
for(reg int i=0;i<ve.size();i++)
{
{
int nu=lower_bound(x,x+lenx,ve[i].a.x)-x+1;
int c=ve[i].c>2?-1:ve[i].c;
update(1,lenx,nu,c,1);
}
else
{
ans=0;
int l=lower_bound(x,x+lenx,ve[i].a.x)-x+1;
int r=lower_bound(x,x+lenx,ve[i].b.x)-x+1;
query(1,lenx,l,r,1);
res+=ans;
}
}
return res;
}
int main()
{
freopen("data.txt","r",stdin);
init();
scanf("%d",&q);
Point a,b;
while(q--)
{
scanf("%lf%lf",&a.x,&a.y);
scanf("%lf%lf",&b.x,&b.y);
if(a.x>b.x||a.y>b.y){swap(a,b);}
if(a.x!=b.x)
{
x[lenx++]=a.x;x[lenx++]=b.x;
ve.pb(Seg(a,b,2));
}
else
{
x[lenx++]=a.x;
ve.pb(Seg(a,a,1));
ve.pb(Seg(b,b,3));
}
}
printf("%d\n",slove());
return 0;
}