poj3304 Segments【计算几何】-白红宇

poj3304 Segments【计算几何】

阅读量：5217 次

发布时间：2019-06-14

本文共 1943 字，大约阅读时间需要 6 分钟。

最近开始刷计算几何了公式好多完全不会

数学不行几何不行记忆力不行当机

查的题解就当复习吧这套专题拿来熟悉一下计算几何模板

#include 
    
     #include
     
      #include
      
       using namespace std;const double eps = 1e-8;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 xx, double yy):x(xx), y(yy){}    point operator -(const point &a) const{        return point(x - a.x, y - a.y);    }    double operator ^(const point &a) const{        return x * a.y - y * a.x;    }    double operator *(const point &a) const{        return x * a.x + y * a.y;    }};struct line{    point s, e;    line(){}    line(point ss, point ee):s(ss), e(ee){}};double xmult(point p0, point p1, point p2)//判断p0是否在p1-p2直线上{    return (p1 - p0) ^ (p2 - p0);}bool seg_line(line a, line b){    return sgn(xmult(b.s, a.s, a.e) * sgn(xmult(b.e, a.s, a.e))) <= 0;//线段b的两个端点在直线a的两端}double dist(point a, point b){    return sqrt((b - a) * (b - a));}const int maxn = 110;line ll[maxn];bool check(line a, int n){    if(sgn(dist(a.s, a.e))== 0) return false;    for(int i = 0; i < n; i++){        if(seg_line(a, ll[i]) == 0)            return false;    }    return true;}int main(){    int n, t;    cin>>t;    while(t--){        cin>>n;        double x1, x2, y1, y2;        for(int i = 0; i < n; i++){            cin>>x1>>y1>>x2>>y2;            ll[i] = line(point(x1, y1), point(x2, y2));        }        int flag = 0;        for(int i = 0; i < n; i++){            for(int j = 0; j < n; j++){                if(check(line(ll[i].s, ll[j].s), n) || check(line(ll[i].s, ll[j].e), n)||                   check(line(ll[i].e, ll[j].s), n) || check(line(ll[i].e, ll[j].e), n)){                        flag = true;//找到了一条直线可以和所有的线段相交                        break;                   }            }        }        printf("%s\n", flag ? "Yes!" : "No!");    }    return 0;}