/**//* 题意:求是否存在一条直线,使所有线段到这条直线的投影至少有一个交点 可以在共同投影处作原直线的垂线,则该垂线与所有线段都相交 <==> 是否存在一条直线与所有线段都相交
可以枚举线段的端点作为直线的(注意如果相同构不成直线) 然后判断所有线段是否都与之相交
这种做法我也不是很懂,可能这条直线能将所有点分成位于直线两端的两部分吧 */ #include<cstdio> #include<cstdlib> #include<cmath>
const double esp=1e-8; const int MAXN=210;
struct Point{ double x,y; }points[MAXN];
bool isEqual(double &a,double &b){ return fabs(a-b)<esp; } double mul(Point &a,Point &b,Point &o){ return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } int main(){ //freopen("in","r",stdin); int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=2*n;i+=2) scanf("%lf%lf%lf%lf",&points[i].x,&points[i].y,&points[i+1].x,&points[i+1].y);
bool flag=false; for(int i=1;i<=2*n&&!flag;i++)//enum line for(int j=1;j<=2*n;j++){ Point p1=points[i],p2=points[j]; if(isEqual(p1.x,p2.x)&&isEqual(p1.y,p2.y))continue; //chk int k; for(k=1;k<=2*n;k+=2) if(mul(points[k],p1,p2)*mul(points[k+1],p1,p2)>esp)break; if(k>=2*n){flag=true;break;} } printf(flag?"Yes!\n":"No!\n"); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|