本文主要是介绍POJ 3304 Segments 【计算几何】【直线和线段的关系】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3304
题目大意：T个case，每个case里面有N条线段，判断能否存在一条直线，使得所有的线段在这条直线上都能有公共点，如果存在输出Yes，否则输出No。
题目的意思可以变成，在N条直线的2*N个端点中选择两个点组成一条直线能否满足这个条件，暴力枚举即可，注意的一点是在枚举的2*n个点中每次选择的两个点要判断是不是重复的。
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<stdlib.h>
using namespace std;#define eps 1e-8
#define zero(x) (((x)>0? (x):-(x))<eps) //是0则返回1，否则返回0
#define _sign(x) ((x)>eps? 1:((x)<-eps? 2:0))//负数 0 正数 分别返回 2 0 1struct point {double x;double y;point(const double &x = 0, const double &y = 0):x(x), y(y){}void in(){ scanf("%lf %lf", &x, &y); }void out()const{ printf("%.2f %.2f\n",x, y);}
};
struct line {point a,b;line(const point &a = point(), const point &b = point()):a(a), b(b){}void in(){ a.in(); b.in();}void out()const{ a.out(); b.out(); }
};
//计算叉乘(P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){ //p0是中间return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}//判两点在直线同侧,是的话返回1
int same_side(point p1,point p2,line l){return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}line L[105];
point P[500];
int N;
int judge(line LL){if( _sign(LL.a.x-LL.b.x)==0 && _sign(LL.a.y-LL.b.y)==0 ) return 0;for(int i=0;i<N;i++){if(same_side(L[i].a,L[i].b,LL)==1) return 0;}return 1;
}int main ()
{int T;scanf("%d",&T);while(T--){scanf("%d",&N);for(int i=0;i<N*2;i++) P[i].in();for(int i=0;i<N;i++){L[i].a=P[i*2];L[i].b=P[i*2+1];}int flag = 0;for(int i=0;i<N*2-1;i++)for(int j=i+1;j<N*2;j++){line LL;LL.a=P[i];LL.b=P[j];if(judge(LL)==1) {flag=1;break;}}if(flag==1) cout<<"Yes!"<<endl;else cout<<"No!"<<endl;}
}
这篇关于POJ 3304 Segments 【计算几何】【直线和线段的关系】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
