HDU 5862 Counting Intersections 扫描线+树状数组

时间：2022-11-27 20:59:19

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5862

Counting Intersections

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
#### 问题描述
> 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.
#### 输入
> 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 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

题意

给你若干个平行于坐标轴的，长度大于0的线段，且任意两个线段没有公共点，不会重合覆盖。问有多少个交点。

题解

扫描线+树状数组

首先把平行于x轴的线段和平行于y轴的线段分开存。对于平行于y轴的线段，我们按它的上端点排降序，对于平行于x轴的线段，我们按照它们的高度排降序。

然后我们遍历一遍平行于x轴的线段，考虑有多少条线段与当前遍历的平行于x轴的线段所在的直线相交的线段，并且更新到树状数组中，那么与当前平行于x轴的线段相交的垂直线段为sum(r)-sum(l-1),l、r分别为当前线段的左右端点。

那么，如何维护与某条直线相交的垂直线段呢？

由于我们遍历平行于x轴的直线是按高度从高到低的，对于上端点高于当前遍历高度的所有垂直线段都压到树状数组中，并且把它们的下端点（大的优先）压到优先队列中，然后再从优先队列中踢掉下端点大于当前遍历高度的，同时更新树状数组（删除操作）。

由于数据范围比较大，横坐标需要离散化。

代码

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) ;//cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define reu(i,a,b) for(int i=a;i<=(b);i++)

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

//start----------------------------------------------------------------------

const int maxn=4e5+10;

LL sumv[maxn];

struct Node{

	int val,u,v;

	Node(int val,int u,int v):val(val),u(u),v(v){}

	bool operator < (const Node& tmp) const {

		return val>tmp.val;

	}

};

bool cmp(const Node& n1,const Node& n2){

	return n1.v>n2.v;

}

LL sum(int x){

	LL ret=0;

	while(x>0){

		ret+=sumv[x];

		x-=(x&-x);

	}

	return ret;

}

void add(int x,int v){

	while(x<maxn){

		sumv[x]+=v;

		x+=(x&-x);

	}

}

VI ha;

vector<Node> col,row;

int n;

void init(){

	ha.clear();

	col.clear();

	row.clear();

	clr(sumv,0);

}

int main() {

	int tc;

	scanf("%d",&tc);

	while(tc--){

		scanf("%d",&n);

		init();

		rep(i,0,n){

			int u1,v1,u2,v2;

			scanf("%d%d%d%d",&u1,&v1,&u2,&v2);

			if(u1==u2){

				if(v1>v2) swap(v1,v2);

				col.push_back(Node(u1,v1,v2));

			}else{

				if(u1>u2) swap(u1,u2);

				row.push_back(Node(v1,u1,u2));

			}

			ha.push_back(u1);

			ha.push_back(u2);

		}

		sort(all(ha));

		ha.erase(unique(all(ha)),ha.end());

		sort(all(col),cmp);

		sort(all(row));

		priority_queue<pair<int,int> > pq;

		int p=0;

		LL ans=0;

		rep(i,0,row.sz()){

			int hi=row[i].val;

			bug(hi);

			while(p<col.sz()&&col[p].v>=hi){

				int id=lower_bound(all(ha),col[p].val)-ha.begin()+1;

				pq.push(mkp(col[p].u,id));

				add(id,1);

				p++;

			}

			while(!pq.empty()&&pq.top().X>hi){

				add(pq.top().Y,-1);

				pq.pop();

			}

			int l=lower_bound(all(ha),row[i].u)-ha.begin()+1;

			int r=lower_bound(all(ha),row[i].v)-ha.begin()+1;

			ans+=sum(r)-sum(l-1);

		}

		printf("%lld\n",ans);

	}

	return 0;

}

//end-----------------------------------------------------------------------

/*

4

1 0 1 1

0 1 2 1

3 1 3 2

1 2 1 3

*/

相关文章