51Nod 1264：线段相交（计算几何）

痛定思痛。 2021-12-21 03:35 260阅读 0赞

# 51Nod 1264：线段相交 #

## Decision ##

给出平面上两条线段的两个端点，判断这两条线段是否相交（有一个公共点或有部分重合认为相交）。 如果相交，输出"Yes"，否则输出"No"。

## Input ##

第1行：一个数T，表示输入的测试数量(1 <= T <= 1000)  
第2 - T + 1行：每行8个数，x1,y1,x2,y2,x3,y3,x4,y4。(-10^8 <= xi, yi <= 10^8)  
(直线1的两个端点为x1,y1 | x2, y2,直线2的两个端点为x3,y3 | x4, y4)

## Output ##

输出共T行，如果相交输出"Yes"，否则输出"No"。

## 输入样例 ##

2
    1 2 2 1 0 0 2 2
    -1 1 1 1 0 0 1 -1

## 输出样例 ##

Yes
    No

## Solve ##

跨立实验  
如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) \* ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) \* ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) \* ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) \* ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示：  
![Geometry\_2.gif][Geometry_2.gif]  
（以上摘自 \[[https://dev.gameres.com/Program/Abstract/Geometry.htm\#%E5%88%A4%E6%96%AD%E4%B8%A4%E7%BA%BF%E6%AE%B5%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4][https_dev.gameres.com_Program_Abstract_Geometry.htm_E5_88_A4_E6_96_AD_E4_B8_A4_E7_BA_BF_E6_AE_B5_E6_98_AF_E5_90_A6_E7_9B_B8_E4_BA_A4]\]）

## Code ##

/*************************************************************************
    
         > Author: WZY
         > School: HPU
         > Created Time:   2019-06-25 17:43:54
         
    ************************************************************************/
    #include <bits/stdc++.h>
    #define ll long long
    #define ull unsigned long long
    #define ms(a,b) memset(a,b,sizeof(a))
    const int inf=(1<<30);
    const ll INF=(1LL*1<<60);
    const int maxn=1e6+10;
    const int mod=1e9+7;
    const int maxm=1e3+10;
    using namespace std;
    struct node
    {
        double x,y;
    }p[maxn];
    double cel(node a,node b,node c)
    {
        return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
    }
    int main(int argc, char const *argv[])
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
            freopen("out.txt", "w", stdout);
        #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            for(int i=0;i<4;i++)
                cin>>p[i].x>>p[i].y;
            if(cel(p[0],p[1],p[2])*cel(p[0],p[1],p[3])<=0&&cel(p[2],p[3],p[0])*cel(p[2],p[3],p[1])<=0)
                cout<<"Yes\n";
            else
                cout<<"No\n";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Friends-A/p/11085384.html

[Geometry_2.gif]: https://i.loli.net/2019/06/25/5d1211e2402af25383.gif
[https_dev.gameres.com_Program_Abstract_Geometry.htm_E5_88_A4_E6_96_AD_E4_B8_A4_E7_BA_BF_E6_AE_B5_E6_98_AF_E5_90_A6_E7_9B_B8_E4_BA_A4]: https://dev.gameres.com/Program/Abstract/Geometry.htm#%E5%88%A4%E6%96%AD%E4%B8%A4%E7%BA%BF%E6%AE%B5%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4