POJ-2653-Pick-up sticks（暴力，线段相交）

题目大意：按顺序给出n条线段，每条线断按输入顺序放置，求最后在最上面的下线段的编号（最上面的线段数量<=1000）。

思路：n的范围1e5，m的范围1e3，想着O(n^2)的算法不行，那怕给了3000ms，

开始就想到了一个假算法：一开始是想着从后往前走，维护一个最上面的线的集合。从后往前读，遇到一条线，如果和最上面的线没有相交的话，放入集合中，最后答案就是集合中的线段（乍一看O(nm)1e5*1e3的复杂度,勉勉强强应该能过，谁知是个假算法。：如图所示，先放3号，2号判断不通过不放，再放1号的时候就判断通过了。一开始没有想到，就一直WA。。

想来想去只会一个暴力。没什么好的想法。就去讨论区看了看，发现基本也都是暴力的。。。

就用暴力水一发吧。感觉这个题很没意思。。

如果有大佬有更好的算法，请务必留言告诉我，十分感谢！。

ACCode：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include<stdio.h>
#include<string.h> 
#include<math.h> 
   
#include<map>  
#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
#define ll long long 
#define Pair pair<int,ll>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double EPS=1.0e-8;
const double PI=acos(-1.0);

struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
	friend Point operator + (const Point &a,const Point &b){
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator - (const Point &a,const Point &b){
		return Point (a.x-b.x,a.y-b.y);
	}
	friend double operator ^ (const Point &a,const Point &b){
		return a.x*b.y-a.y*b.x;
	}
	friend bool operator == (const Point &a,const Point &b){
		return fabs(a.x-b.x)<EPS&&fabs(a.y-b.y)<EPS;
	}
};
struct V{
	Point start,end;double Ang;int Id;
	V(Point _start=Point(0,0),Point _end=Point(0,0),int _Id=0,double _Ang=0){
		start=_start;end=_end;Id=_Id;Ang=_Ang;
	}
};
V Line[MAXN];int Vis[MAXN],Top;
int n;

int LineInter(V l1,V l2){
	if(max(l1.start.x,l1.end.x)>=min(l2.start.x,l2.end.x)&&
	max(l2.start.x,l2.end.x)>=min(l1.start.x,l1.end.x)&&
	max(l1.start.y,l1.end.y)>=min(l2.start.y,l2.end.y)&&
	max(l2.start.y,l2.end.y)>=min(l1.start.y,l1.end.y)){
		if(((l2.end-l2.start)^(l1.start-l2.start))*((l2.end-l2.start)^(l1.end-l2.start))<=0&&
		((l1.end-l1.start)^(l2.start-l1.start))*((l1.end-l1.start)^(l2.end-l1.start))<=0)
			return 1;
	}return 0;
}
int Cmp(V a,V b){
	return a.Id<b.Id;
}
int main(){
	while(~scanf("%d",&n)){
		if(n==0) break;
		clean(Vis,0);
		for(int i=1;i<=n;++i){
			double x1,x2,y1,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			Line[i]=V(Point(x1,y1),Point(x2,y2),i);
		}Top=0;
		for(int i=n;i>=1;--i){
			int flag=1;
			for(int j=i+1;j<=n;++j){
				if(LineInter(Line[i],Line[j])){
					flag=0;break;
				}
			}
			if(flag) Vis[i]=1;
		}printf("Top sticks: ");
		int first=1;
		for(int i=1;i<=n;++i){
			if(Vis[i]&&first){
				printf("%d",i);first=0;
			}
			else if(Vis[i]) printf(", %d",i);
		}printf(".\n");
	}
}

/*

*/