本文主要是介绍poj 2653 几何，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
按顺序给一系列的线段，问最终哪些线段处在顶端（俯视图是完整的）。
const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
}struct Point{double x , y ;Point(){}Point(double _x , double _y):x(_x),y(_y){}Point operator + (Point o){return Point(add(x , o.x) , add(y , o.y)) ;}Point operator - (Point o){return Point(add(x , -o.x) , add(y , -o.y)) ;}double operator ^(Point o){return add(x*o.y , -y*o.x) ;}void read(){scanf("%lf%lf" ,&x , &y) ;}
};int onseg(Point s , Point t , Point p){return ((s-p).x * (t-p).x <= 0) && ((s-p).y * (t-p).y <= 0) ;
}int intersection(Point p1 , Point p2 , Point q1 , Point q2){double d1 = (p2 - p1) ^ (q1 - p1) ;double d2 = (p2 - p1) ^ (q2 - p1) ;double d3 = (q2 - q1) ^ (p1 - q1) ;double d4 = (q2 - q1) ^ (p2 - q1) ;if(d1==0 &&onseg(p1,p2,q1)) return 1 ;if(d2==0 &&onseg(p1,p2,q2)) return 1 ;if(d3==0 &&onseg(q1,q2,p1)) return 1 ;if(d4==0 &&onseg(q1,q2,p2)) return 1 ;if(d1*d2 < 0 && d3*d4 < 0) return 1 ;return 0 ;
}struct Line{Point s , t ;Line(){}Line(Point _s , Point _t):s(_s),t(_t){}int intersect(Line o){return intersection(s , t , o.s , o.t) ;}void read(){s.read() , t.read() ;}
};vector<int> lis ;
vector<int> ::iterator it ;
Line line[100008] ;int main(){int i , j , n ; while(cin>>n && n){for(i = 1 ; i <= n ; i++) line[i].read() ;lis.clear() ;for(i = 1 ; i <= n ; i++){ for(it = lis.begin() ; it != lis.end() ; ){if(line[i].intersect(line[*it]))it = lis.erase(it) ;else it++ ;}lis.push_back(i) ;}printf("Top sticks: ") ;for(i = 0 ; i < lis.size() -1 ; i++) printf("%d, " , lis[i]) ;printf("%d.\n" , lis[i]) ; }return 0 ;
}
这篇关于poj 2653 几何的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
