poj 2653 Pick-up sticks--线段相交--vector
2012-08-15 09:25:16

[cpp]
/*

*/
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const double esp=1e-8;
struct point

double x,y;
};
struct node

point p1,p2;
int no;
};
vector<node>v;
int n;
node cc;
double max(double a,double b){return a>b?a:b;}
double min(double a,double b){return a<b?a:b;}
double cross(point p,point s,point e)

return (e.x-s.x)*(p.y-s.y)-(p.x-s.x)*(e.y-s.y);

bool segintersect(point s1,point e1,point s2,point e2)

return((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))&&
(cross(s1,s2,e2)*cross(e1,s2,e2)<=esp)&&
(cross(s2,s1,e1)*cross(e2,s1,e1)<=esp));

bool ok(node n)

if(segintersect(n.p1,n.p2,cc.p1,cc.p2))
return true;
return false;

int main()

int i;
while(scanf("%d",&n),n)
{
v.erase(v.begin(),v.end());
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&cc.p1.x,&cc.p1.y,&cc.p2.x,&cc.p2.y);
cc.no=i;
v.erase(remove_if(v.begin(),v.end(),ok),v.end());
v.push_back(cc);
}
printf("Top sticks: ");
for(vector<node>::iterator it = v.begin(); it!= v.end(); it++)
{
printf("%d",it->no);
if(it!=v.end()-1)
printf(", ");
else printf(".\n");
}
} www.2cto.com
return 0;