3115301_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <list>
#include <algorithm>

using namespace std;

struct point
{
	double x, y;
};

struct segment
{
	int id;
	point a, b;
};

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

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

double multi(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool isIntersected(point s1,point e1,point s2,point e2)
{

    if(
		(max(s1.x, e1.x) > min(s2.x, e2.x)) &&
		(max(s2.x, e2.x) > min(s1.x, e1.x)) &&
		(max(s1.y, e1.y) > min(s2.y, e2.y)) &&
		(max(s2.y, e2.y) > min(s1.y, e1.y)) &&
		(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
		(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
	 )
	 return true;
	 return false;
}

int main()
{
	int n, i;
	segment s;
	list <segment> top;
	list <segment> ::iterator it, ti;

	while(scanf("%d",&n)==1,n)
	{
		printf("Top sticks:");
		top.clear();
		for(i = 1; i <= n; i++)
		{
			s.id = i;
			scanf("%lf%lf%lf%lf",&s.a.x,&s.a.y,&s.b.x,&s.b.y);
			if(top.empty())
				top.push_back(s);
			else
			{
				for(it = top.begin(); it != top.end(); it++)
				{
					if(isIntersected((*it).a,(*it).b,s.a,s.b))
					{
						it = top.erase(it);
					}
					
				}
				top.push_back(s);
			}
		}
		for(it = top.begin(); it != top.end(); )
		{
			printf(" %d",(*it).id);
			it++;
			if(it!=top.end())
				printf(",");
		}
		printf(".\n");
	}
	return 0;
}