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