HDU 5862 Counting Intersections 扫描线

传送门：HDU5862

因为题目已经说明所有的线段都是平行于坐标轴的

那么,线段无外乎两种:①平行于x轴;②平行于y轴

那交点必定只有竖向与横向的线段才会产生

另外,此题数据规模显然是不允许我们进行O(n^2)的暴力求解

那我们可以将横向的线段与竖向线段分开处理

对于横向的线段,我们只保留端点

再按x从小到大排序,x相等的情况下,左端点优先于右端点

而竖向的线段同样按x从小到大排序,但是不拆分成两个端点,而是保留整条线段

然后枚举竖向线段,将小于该竖向线段横坐标的所有点进行处理

若点为左端点,则在其对应的值处的树状数组做+1操作,若为右端点,则做-1操作

这保证了对于第i条竖向线段,当前树状数组中记录了横坐标横跨该竖向线段的线段数量（至于相不相交就要看横线的纵坐标在不在竖线的范围内了）

以上转自：http://blog.csdn.net/just_sort/article/details/52244981

蒟蒻刚学扫描线，感觉上面这篇题解介绍的挺到位的，让我也大致了解了扫描线的思想，所以就无耻的CV了。

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef pair<int,int>P;
const int MAXN=400010;
struct node1{
	int x,y,type;
	bool operator < (node1 a)const
	{
		if(x==a.x)
		return type<a.type;
		return x<a.x;
	}
}r[MAXN];
struct node2{
	int x1,y1,x2,y2;
	bool operator < (node2 a)const
	{
		return x1<a.x1;
	}
}c[MAXN],seg[MAXN];
ll bit[MAXN];
int Hash[MAXN];
ll b_sum(int i)
{
	ll ans=0;
	while(i>0)
	{
		ans+=bit[i];
		i-=i&-i;
	}
	return ans;
}
void b_add(int i,int x)
{
	while(i<MAXN)
	{
		bit[i]+=x;
		i+=i&-i;
	}
}
int main()
{
	int T,n,cnt;
	scanf("%d",&T);
	while(T--)
	{
		cnt=1;//cnt初始化为1是因为树状数组下标从1开始
		memset(bit,0,sizeof(bit));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&seg[i].x1,&seg[i].y1,&seg[i].x2,&seg[i].y2);
			if(seg[i].x1>seg[i].x2||seg[i].y1>seg[i].y2)
			{
				swap(seg[i].x1,seg[i].x2);
				swap(seg[i].y1,seg[i].y2);
			}
			Hash[cnt++]=seg[i].x1;
			Hash[cnt++]=seg[i].y1;
			Hash[cnt++]=seg[i].x2;
			Hash[cnt++]=seg[i].y2;
		}
		sort(Hash+1,Hash+cnt);
		cnt=unique(Hash+1,Hash+cnt)-Hash;
		int x1,y1,x2,y2,cnt1=0,cnt2=0;
		for(int i=1;i<=n;i++)
		{
			x1=lower_bound(Hash+1,Hash+cnt,seg[i].x1)-Hash;
			y1=lower_bound(Hash+1,Hash+cnt,seg[i].y1)-Hash;
			x2=lower_bound(Hash+1,Hash+cnt,seg[i].x2)-Hash;
			y2=lower_bound(Hash+1,Hash+cnt,seg[i].y2)-Hash;
			if(x1==x2)
			c[cnt2++]=node2{x1,y1,x2,y2};
			if(y1==y2)
			{
				r[cnt1].x=x1,r[cnt1].y=y1,r[cnt1++].type=0;
				r[cnt1].x=x2,r[cnt1].y=y2,r[cnt1++].type=1;
			}
		}
		sort(r,r+cnt1);
		sort(c,c+cnt2);
		ll ans=0;
		for(int i=0,j=0;i<cnt2;i++)
		{
			while(j<cnt1&&(r[j].x<c[i].x1||(r[j].x==c[i].x1&&r[j].type==0)))//注意横线右端点和竖线相交的情况不能进入while
			{
				if(r[j].type)
				b_add(r[j].y,-1);
				else
				b_add(r[j].y,1);
				j++;
			}
			ans+=b_sum(c[i].y2)-b_sum(c[i].y1-1);//在竖线纵坐标范围内
		}
		printf("%lldn",ans);
	}
    return 0;
}

最后

以上就是腼腆小馒头为你收集整理的HDU 5862 Counting Intersections 扫描线的全部内容，希望文章能够帮你解决HDU 5862 Counting Intersections 扫描线所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。