本文主要是介绍poj 3304 Segments（计算几何：叉积），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目给出多条线段，问是否存在一条直线
使得所有投射到这条直线的线段至少有一个交点
也即判断是否存在一条直线与所有线段都相交
假设存在一条直线与所有线段都相交，那么我们一定可以通过平移、旋转等处理
使这条直线与两条或多条线段交于线段的端点处
我们就可以通过枚举所有端点再判断这样的直线是否满足条件即可
代码如下：
/* ***********************************************Author :yinhuaEmail :yinwoods@163.comFile Name :poj3304.cppCreated Time :2014年12月02日 星期二 16时52分02秒************************************************ */#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110
#define eps 1e-6
#define LL long long
using namespace std;int sgn(double x) {if(fabs(x) < eps) return 0;if(x < 0) return -1;return 1;
}struct Point {double x, y;Point() {}Point(double _x, double _y) {x = _x; y = _y;}Point operator - (const Point &b) const {return Point(x-b.x, y-b.y);}double operator *(const Point &b) const {return x*b.x + y*b.y;}double operator ^(const Point &b) const {return x*b.y - y*b.x;}
};struct Line {Point s, e;Line() {}Line(Point _s, Point _e) {s = _s, e = _e;}
};Line line[MAXN];double xmult(Point p0, Point p1, Point p2) {return (p1-p0)^(p2-p0);
}bool Seg_inter_line(Line l1, Line l2) {return sgn(xmult(l2.s, l1.s, l1.e))*sgn(xmult(l2.e, l1.s, l1.e)) <= 0;
}double dist(Point a, Point b) {return sqrt((b-a)*(b-a));
}bool check(Line l1, int n) {if(sgn(dist(l1.s, l1.e) == 0)) return false;for(int i=0; i<n; ++i) {if(Seg_inter_line(l1, line[i]) == false)return false;}return true;
}int main() {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);line[i] = Line(Point(x1, y1), Point(x2, y2));}bool flag = false;for(int i=0; i<n; ++i) {for(int j=0; j<n; ++j) {if(check(Line(line[i].s, line[j].s), n) || check(Line(line[i].s, line[j].e), n)|| check(Line(line[i].e, line[j].s), n) || check(Line(line[i].e, line[j].e), n)) {flag = true;break;}}}if(flag) puts("Yes!");else puts("No!");}return 0;
}这篇关于poj 3304 Segments（计算几何：叉积）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
