/* * POJ_2653.cpp * * Created on: 2013年11月16日 * Author: Administrator */ #include <iostream> #include <cstdio> #include <cmath> using namespace std; const double epsi = 1e-10; const double pi = acos(-1.0); const int maxn = 100005;//这个不要开得太小... struct Point{ double x,y; Point(double _x = 0,double _y = 0):x(_x),y(_y){ } Point operator-(const Point& op2)const{//**要注意这种写法 return Point(x - op2.x,y - op2.y); } double operator^(const Point& op2)const{ return x*op2.y - y*op2.x; } }p1[maxn],p2[maxn]; int sign(const double& x){//判断x是正数还是负数 if(x > epsi){ return 1;//传入的数是一个整数... }else if(x < -epsi){ return -1;//传入的数是一个负数... } return 0; } double sqr(double x){//计算一个数的平方数 return x*x; } double mul(const Point& p0,const Point& p1,const Point& p2){//计算p0p1与p1p2的叉积叉积 return (p1-p0)^(p2-p0); } double dis2(const Point& p0,const Point& p1){//返回两个点的距离的平方 return sqr(p0.x - p1.x) + sqr(p0.y - p1.y); } double dis(const Point& p0,const Point& p1){//返回两个点的距离 return sqrt(dis2(p0,p1)); } int cross(const Point& p1,const Point& p2,const Point& p3,const Point& p4){//判断p1p2是否跨立p3p4 double a1 = mul(p1,p2,p3); double a2 = mul(p1,p2,p4); if(sign(a1) == 0 && sign(a2) == 0){//如果这两根木棒重合 return 2; } if(sign(a1) == sign(a2)){//如果这两根木棒在同一个方向(同一边) return 0; } return 1;//p1p2和p3p4通过跨立实验 } int main(){ int n; while(scanf("%d",&n)!=EOF,n){ int i; for(i = 1 ; i <= n ; ++i){ scanf("%lf%lf%lf%lf",&p1[i].x,&p1[i].y,&p2[i].x,&p2[i].y); } printf("Top sticks:"); int j; bool f1 = false; for(i = 1 ; i <= n ; ++i){//遍历每一个木棒i,遍历它上面的每一根木棒j,判断他们是否相交 bool flag = false; for(j = i+1 ; j <= n ; ++j){ if(cross(p1[i],p2[i],p1[j],p2[j]) == 1 && cross(p1[j],p2[j],p1[i],p2[i]) == 1){ flag = true; break; } } if(flag == false && f1 == true){//如果第i跟不帮不相交&&且他不是第一根木棒 printf(","); } if(flag == false){//如果他不相交 printf(" %d",i); f1 = true; } } printf(".\n"); } return 0; }