Counting Intersections

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1915 Accepted Submission(s): 601

Problem Description
Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection.

The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.

Input
The first line contains an integer T, indicates the number of test case.

The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.

Output
For each test case, output one line, the number of intersection.

Sample Input
2
4
1 0 1 3
2 0 2 3
0 1 3 1
0 2 3 2
4
0 0 2 0
3 0 3 2
3 3 1 3
0 3 0 2

Sample Output
4
0

Author
BUPT

扫描线问题。

我们按x排序之后，扫描过去即可。我们每次是竖线时记录答案，每次是横线时就讲横线的y坐标放到树状数组中，每次记录答案就是在这个竖线区间当中的值。

注意排序顺序：横线左端点 > 记录答案 > 横线右端点。（想一下）

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=4e5+10;
int T,n,m,d[N],res,cnt;
vector<int> v;
unordered_map<int,int> mp;
struct node{
	int x1,y1,x2,y2,id;
}t[N];
int cmp(node a,node b){
	return (a.x1==b.x1) ? (a.id>b.id) : (a.x1<b.x1);
}
inline void add(int x,int v){
	for(int i=x;i<N;i+=lowbit(i))	d[i]+=v;
}
inline int ask(int x){
	int res=0;	for(int i=x;i;i-=lowbit(i))	res+=d[i];	return res;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		memset(d,0,sizeof d);	res=cnt=0;	mp.clear();	v.clear();
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			int x1,x2,y1,y2;	scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
			v.push_back(y1);	v.push_back(y2);
			if(x1==x2){
				if(y1>y2)	swap(y1,y2);
				t[++cnt]={x1,y1,x2,y2,0};
			}else{
				if(x1>x2)	swap(x1,x2);
				t[++cnt]={x1,y1,0,0,1};	t[++cnt]={x2,y2,0,0,-1};
			}
		}
		sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
		for(int i=0;i<v.size();i++)	mp[v[i]]=i+2;
		sort(t+1,t+1+cnt,cmp);
		for(int i=1;i<=cnt;i++){
			if(t[i].id==0){
				res+=ask(mp[t[i].y2])-ask(mp[t[i].y1]-1);		continue;
			}
			add(mp[t[i].y1],t[i].id);
		}
		printf("%lld\n",res);
	}
	return 0;
}