poj 1127 Jack Straws（计算几何）

左手的ㄟ右手 2022-07-26 05:28 190阅读 0赞

题意：给出n跟木棍首尾两点坐标，判断任意两个跟木棍是否相连，间接连在一起的也是相连的。

解题思路：  
主要是难在如何判断两根木棍是否有交点

求两直线交点： 假设有线段L1 p1 p2, L2 q1 q2  
p q为端点

先变为直线求其交点

(q2-q1)*(p1+t*(p2-p1)-q1)=0

交点为：p1+((q2-q1)*(q1-p1))/((q2-q1)*(p2-p1))\*(p2-p1)

判断交点点r是否在线段L1与线段L2上

定义内积 p1·p2=x1*x2+y1*y2  
外积 p1×p2=x1*y2-y1*x2  
先根据外积判断(p1-r)·(p2-r)=0判断点是否在直线L1上  
再根据内积判断是否有(p1-r)×(p2-r)<=0表示是否在p1,p2之间

判断出任意两线段的关系后再用floyd求出间接线段的关系即可

记得平行要特殊处理 因为平行直线无交点 所以只需要判断一个线段端点是否在另一个线段即可

代码:

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),-1,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    double EPS=1e-10;
    
    double add(double a,double b)
    {
        if(abs(a+b)<EPS*(abs(a)+abs(b))) return 0;
        else return a+b;
    }
    struct P
    {
        double x,y;
        P() {}
        P(double x,double y) :x(x),y(y) {}
        P operator +(P p)
        {
            return P(add(x,p.x),add(y,p.y));
        }
        P operator -(P p)
        {
            return P(add(x,-p.x),add(y,-p.y));
        }
        P operator *(double d)
        {
            return P(x*d,y*d);
        }
        //内积
        double dot(P p)
        {
            return add(x*p.x,y*p.y);
        }
        //外积
        double det(P p)
        {
            return add(x*p.y,-y*p.x);
        }
    };
    //判断q是否在线段p1 p2 上
    bool on_seg(P p1,P p2,P q)
    {
        return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;
    }
    //计算直线p1 p2 与q1 q2的交点
    P intersection(P p1,P p2, P q1,P q2)
    {
        return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
    }
    int main()
    {
        int n;
        RI(n);
        while(n)
        {
            P p[20],q[20];
            for(int i=0; i<n; i++)
            {
                scanf("%lf %lf",&p[i].x,&p[i].y);
                scanf("%lf %lf",&q[i].x,&q[i].y);
            }
            bool ans[20][20];
            for(int i=0; i<n; i++)
            {
                ans[i][i]=true;
                for(int j=i+1; j<n; j++)
                {
                //判断是否平行
                    if((p[i]-q[i]).det(p[j]-q[j])==0)
                    {
                    //如果平行
                        ans[j][i]=ans[i][j]=on_seg(p[i],q[i],q[j])
                                            ||on_seg(p[i],q[i],p[j])
                                            ||on_seg(p[j],q[j],p[i])
                                            ||on_seg(p[j],q[j],q[i]);
                    }
                    else{
                    P r=intersection(p[i],q[i],p[j],q[j]);
                    ans[i][j]=ans[j][i]=on_seg(p[i],q[i],r)&&on_seg(p[j],q[j],r);
                    }
                }
            }
            //通过floyd判断任意两点是否相连
            for(int k=0;k<n;k++)
                for(int i=0;i<n;i++)
                    for(int j=0;j<n;j++)
                        ans[i][j]|=ans[i][k]&&ans[k][j];
            int a,b;
            RII(a,b);
            while(!(a==0&&b==0))
            {
                printf(ans[a-1][b-1]?"CONNECTED\n":"NOT CONNECTED\n");
                RII(a,b);
            }
            RI(n);
        }
        return  0;
    }