#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const double eps = 1e-8;

struct Point
{
	double x;
	double y;
};

struct Line
{
	Point pa;
	Point pb;
	int index;
};
vector<Line> vec_copy;
vector<Line> vec_index;

double ex(double a)
{
	if(a > eps)
		return 1;
	else if(a < -eps)
		return -1;
	return 0;
}

double max(double a,double b)
{
	return a > b ? a : b;
}

double min(double a,double b)
{
	return a < b ? a : b;
}

double cross(const Point &ep,const Point &op,const Point &sp)
{
	return((op.x - ep.x) * (sp.y - ep.y) - (sp.x - ep.x) * (op.y - ep.y));
}

bool on_segment(const Point &p1,const Point &p2,const Point &p3)
{
	if ( min( p1.x, p2.x ) <= p3.x && p3.x <= max( p1.x, p2.x ) 
		&& min( p1.y, p2.y ) <= p3.y && p3.y <= max( p1.y, p2.y ) )
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool segments_intersect(const Line &L1,const Line &L2)
{
	double d1,d2,d3,d4;
	d1 = ex(cross(L2.pa,L2.pb,L1.pa));
	d2 = ex(cross(L2.pa,L2.pb,L1.pb));
	d3 = ex(cross(L1.pa,L1.pb,L2.pa));
	d4 = ex(cross(L1.pa,L1.pb,L2.pb));

	if(d1 * d2 < 0 && d3 * d4 < 0)
	{
		return true;
	}
	else if(d1 == 0 && on_segment(L2.pa,L2.pb,L1.pa))
	{
		return true;
	}
	else if(d2 == 0 && on_segment(L2.pa,L2.pb,L1.pb))
	{
		return true;
	}
	else if(d3 == 0 && on_segment(L1.pa,L1.pb,L2.pa))
	{
		return true;
	}
	else if(d4 == 0 && on_segment(L1.pa,L1.pb,L2.pb))
	{
		return true;
	}
	return false;
}

int main()
{
	int n;
	while(cin>>n && n)
	{
		Line L;
		vector<Line> line;
		int i;
		vector<Line>::iterator iter;
		cin>>L.pa.x>>L.pa.y>>L.pb.x>>L.pb.y;
		L.index = 1;
		line.push_back(L);
		for(i = 1; i < n; i++)
		{
			cin>>L.pa.x>>L.pa.y>>L.pb.x>>L.pb.y;
			L.index = i + 1;
			int flag = 0;
			for(iter = line.begin(); iter < line.end(); iter++)
			{
				if(segments_intersect(L,*iter))
				{
					line.erase(iter);
				}
			}
			line.push_back(L);
		}
		cout<<"Top sticks: ";
		for(i = 0; i < line.size() - 1; i++)
		{
			cout<<line[i].index<<", ";
		}
		cout<<line[i].index<<"."<<endl;
		
	}
	return 0;
}

• TLE 无疑 (130) FuckYouFuckingMe 2012-01-27 19:55:32