POJ 2653 Pick-up sticks（简单计算几何）

Time Limit: 3000MS Memory Limit: 65536K

这道题的数据范围是$n\le 100000$，其实我也很好奇我是怎么用$O（T{n}^2）$的算法跑过去的，这道题的思路很简单，照着提议模拟一边就可以了，对于每一条线段，我们判断在它之后的线段有没有与它相交的，如果有就打上标记，没有就不打标记，最后把所有没打标记的线段输出就可以了。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
struct pot{double x,y;};
struct line{pot a,b;}l[N];
bool vis[N];
inline double cross(pot a,pot b,pot c){return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}
inline bool across(line m,line n){
	if(cross(m.a,n.b,n.a)*cross(m.b,n.b,n.a)<0&&cross(n.a,m.b,m.a)*cross(n.b,m.b,m.a)<0)return true;
	return false;
}
int n;
int main(){
	while(scanf("%d",&n)==1){
		if(n==0)break;
		for(int i=0;i<n;++i)scanf("%lf%lf%lf%lf",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);
		memset(vis,false,sizeof(vis));
		for(int i=0;i<n;++i){
			if(vis[i])continue;
			for(int j=i+1;j<n;++j){
				if(across(l[i],l[j])){
					vis[i]=true;
					break;
				}
			}
		}
		bool f=false;
		printf("Top sticks:");
		for(int i=0;i<n;++i){
			if(!vis[i]){
				if(!f){printf(" %d",i+1),f=true;}
				else printf(", %d",i+1);
			}
		}
		puts(".");
	}
	return 0;
}