本文主要是介绍poj 3304 几何，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：给出n条线段两个端点的坐标，问所有线段投影到一条直线上，如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。解题思路：如果存在这样的直线，过投影相交点（或投影相交区域中的点）作直线的垂线，该垂线（也是直线）必定与每条线段相交，问题转化为问是否存在一条直线和所有线段相交。
若存在一条直线与所有线段相交，此时该直线必定经过这些线段的某两个端点，所以枚举任意两个端点即可。
这里要注意的地方就是，题目说如果两个点的距离小于1e-8就等价于一点（即重点），所以要考虑重点。
const double eps = 1e-8 ;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) ;}double dist(Point o){return sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y)) ;}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) ;return d1 * d2 <= 0 ;
}struct Line{Point s , t ;Line(){}Line(Point _s , Point _t):s(_s),t(_t){}int intersect(Line o){ // 直线与线段O是否相交return intersection(s , t , o.s , o.t) ;}void read(){s.read() , t.read() ;}friend bool operator < (const Line A ,const Line B){return A.s.x < B.s.x ;}
};int n ;
Point po[208] ;
Line line[108] ;int judge(Line now){for(int k = 1 ; k <= n ; k++){if(! now.intersect(line[k])) return 0 ;}return 1 ;
}int ok(){int i , j , k , s ;Line now ;for(i = 1 ; i <= 2*n ; i++){for(j = i+1 ; j <= 2*n ; j++){if(po[i].dist(po[j]) < eps) continue ;now = Line(po[i] , po[j]) ;if(judge(now)) return 1 ;}}return 0 ;
}int main(){int t , i , j ;cin>>t ;while(t--){cin>>n ;for(i = 1 ; i <= n ; i++){po[i].read() ;po[i+n].read() ;line[i] = Line(po[i] , po[i+n]) ;}if(n == 1){puts("Yes!") ;continue ;}if(ok()) puts("Yes!") ;else puts("No!") ;}return 0 ;
}这篇关于poj 3304 几何的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
