Pick-up sticks POJ2653（线段相交判断）

Pick-up sticksPOJ - 2653

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

Hint

Huge input,scanf is recommended.

分析：

每加入一条新的线段，就判断其能挡住那些线段，然后更新标记，然而数据规模达到10w，如果每次都把之前的线段都看一遍的话，复杂度是n^2，所以我们就要给出适当的优化，注意到一条线段一旦被挡住一次，那么就不可能是最上面的线段了，所以每次判断的时候，先看要判断的线段的标记，如果已经被挡住就不要再判断了；

但是底下的代码里面，我稍微换了一下思路，应用了vector，vector里面只存储没有被挡住的线段，那么同样的结构体线段必须要多一个成员变量num表示它是第几条线段，那么vector的标号就只是代表了还没有被挡住的线段的数量。

注意操作vector要格外小心，首先判断的时候不能删vector的元素，因为一旦删除前面的元素，那么后面的元素对应的标号也会改变，所以要先把需要删除的标号存储起来（我同样使用了vector存储），然后删除的时候 从标号大的开始删，理由跟前面是一样的；

下面来说一说最最关键的如何判断两条线段相交

简单的说就是：快速排斥+跨立实验

1.快速排斥：构建两条线段对应的矩形，判断矩形是否有重叠，有则通过快速排斥，否则不通过，即使是贴在一起也不通过

实现方法就是一个矩形x（y）坐标的最大值不能小于等于另一个矩形的对应坐标的最小值

2.跨立实验：两条直线对另外一条分别都要判断，保证一条直线的两个端点在另一条直线的两侧

实现方法用叉乘，注意有等于零的特殊情况，但是只有一种等于零的情况要单独说一下，其余的都可以认为是端点在线段上；而这种特殊情况，不过是两条线段共线，且无重叠，而这种情况肯定通过不了快速排斥，也就不用考虑了

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const double eps=1e-8;
struct Vector{
	double x,y;
	Vector(){}
	Vector(double x,double y):x(x),y(y){}
};
typedef Vector point;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,Vector b){return Vector(a.x*b.x,a.y*b.y);}
Vector operator / (Vector a,Vector b){return Vector(a.x/b.x,a.y/b.y);}
double dot(Vector a,Vector b){
	return a.x*b.x+a.y*b.y;
}
double cross(Vector a,Vector b){
	return a.x*b.y-a.y*b.x;
}
struct line{
	point p1,p2;
	int num;
	line(){}
	line(point p1,point p2,int num):p1(p1),p2(p2),num(num){} 
};
vector<line> v;
int flag[100010];
bool is_inter(int a,int b){
	point pa1=v[a].p1,pa2=v[a].p2,pb1=v[b].p1,pb2=v[b].p2;
	if(max(pa1.x,pa2.x)<=min(pb1.x,pb2.x)
	||max(pb1.x,pb2.x)<=min(pa1.x,pa2.x)
	||max(pa1.y,pa2.y)<=min(pb1.y,pb2.y)
	||max(pb1.y,pb2.y)<=min(pa1.y,pa2.y))return false;
	if(cross(pa2-pa1,pb1-pa1)*cross(pa2-pa1,pb2-pa1)<=0
	&&cross(pb2-pb1,pa1-pb1)*cross(pb2-pb1,pa2-pb1)<=0)return true;
	else return false;
}
int main(){
	int n;
	scanf("%d",&n);
	while(n){
		memset(flag,0,sizeof(flag));
		for(int i=0;i<n;i++){
			double X1,Y1,X2,Y2;
			scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
			v.push_back(line(point(X1,Y1),point(X2,Y2),i));
			flag[i]=1;
			vector<int> nv;
			for(int j=0;j<v.size()-1;j++){
				if(is_inter(v.size()-1,j)){
					flag[v[j].num]=0;
					nv.push_back(j);
				}
			}
			for(int j=nv.size()-1;j>=0;j--){
				v.erase(v.begin()+nv[j]);
			}
			nv.clear();
		}
		printf("Top sticks: ");
		int ok=0;
		for(int i=0;i<n;i++){
			if(flag[i]){
				if(ok==0){
					printf("%d",i+1);
					ok++;
				}
				else{
					printf(", %d",i+1);
				}	
			}
		}
		printf(".\n");
		v.clear();
		scanf("%d",&n);
	}
	return 0;
}