首页 > 代码库 > POJ 3304 Segments 叉积
POJ 3304 Segments 叉积
题意：
找出一条直线，让给出的n条线段在这条直线的投影至少有一个重合的点
转化一下，以重合的点作垂线，那么这条直线一定经过那n条线段。现在就是求找到一条直线，让这条直线经过所有线段
分析：
假设存在这一条直线，我们以无穷远处作为支点，然后旋转，直到碰到一个线段的端点就停止旋转，此时还是穿过了所有线段；
然后以这个端点为支点，旋转直线，直到碰到一个线段的端点就停止旋转，此时也穿过了所有线段。
于是就证明了，如果直线与所有线段相交，那么必定存在一条直线经过线段中的两个端点
那么，接下来枚举即可。注意要把重复的点去掉
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-8using namespace std;const int maxn=100+5;struct Point{ double x,y; Point() {}; Point(double xx,double yy) { x=xx; y=yy; }} pot[maxn*2];double crs_prdct(Point a,Point b){ return a.x*b.y-b.x*a.y;}Point sub(Point a,Point b){ return Point(a.x-b.x,a.y-b.y);}int main(){// freopen("in.txt","r",stdin); int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); double x1,y1,x2,y2; for(int i=0; i<n; i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); pot[2*i]=Point(x1,y1); pot[2*i+1]=Point(x2,y2); } bool flag; for(int i=0; i<2*n; i++) { for(int j=i+1; j<2*n; j++) { if(pot[i].x==pot[j].x && pot[i].y==pot[j].y) continue; flag=true; for(int k=0; k<n; k++) { double tmp1=crs_prdct(sub(pot[2*k],pot[i]),sub(pot[2*k],pot[j])); double tmp2=crs_prdct(sub(pot[2*k+1],pot[i]),sub(pot[2*k+1],pot[j])); if(fabs(tmp1)<eps || fabs(tmp2)<eps || tmp1*tmp2<0) continue; flag=false; break; } if(flag) break; } if(flag) break; } printf("%s\n",flag? "Yes!":"No!"); } return 0;}
POJ 3304 Segments 叉积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。