ACM刷题之路（六）直线相交问题 POJ3304 Segments

逃离我推掉我的手 2024-02-18 22:18 4阅读 0赞

题目链接：[http://poj.org/problem?id=3304][http_poj.org_problem_id_3304]

### 题目： ###

Description

Given *n* segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number *T* showing the number of test cases and then, *T* test cases follow. Each test case begins with a line containing a positive integer *n* ≤ 100 showing the number of segments. After that, *n* lines containing four real numbers *x*1 *y*1 *x*2 *y*2 follow, in which (*x*1, *y*1) and (*x*2, *y*2) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers *a* and *b* are equal if |*a* \- *b*| < 10-8.

Sample Input

3
    2
    1.0 2.0 3.0 4.0
    4.0 5.0 6.0 7.0
    3
    0.0 0.0 0.0 1.0
    0.0 1.0 0.0 2.0
    1.0 1.0 2.0 1.0
    3
    0.0 0.0 0.0 1.0
    0.0 2.0 0.0 3.0
    1.0 1.0 2.0 1.0

Sample Output

Yes!
    Yes!
    No!

### **题目大意：** ###

3（ t 组数）

2 （n 接下来有n条线段）

1.0 2.0 3.0 4.0 （分别是x1，y1，x2，y2）

4.0 5.0 6.0 7.0

**问 是否存在一条直线，使得该直线和所有以上线段都相交。**

首先，我们来看点积的几何意义：

**设存在a向量和b向量**

**a·b>0 则a、b向量方向相同；**

**a·b=0 则a、b向量相互垂直；**

**a·b<0 则a、b向量方向相反；**

此时聪明的读者已经明白，叉积也有它的几何意义：

设存在点P1,P2,P3；（因为赶高铁时间紧，直接放图片）

跟线性代数求行列式一样，**叉积的计算方法就是求行列式**；

因为叉积的结果是向量，我们**只需要判断结果向量的正负性**即可，所以我们忽略单位i和j，（因为i、j都是单位向量且方向是正）

所以**只要写一个函数，判断正负性即可**，代码如图片下：

![70][]

double det(Point p1,Point p2,Point p3)
    {
        return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y);//判断点p3是否在线段p1p2的左右
        //  x1y2+x3y1+x2y3-x3y2-x2y1-x1y3  不要这样直接乘..可能会爆掉
    }

**该代码是计算叉积。**

**如果a叉积b大于0 则p2p3 在p1p3的逆时针方向反之是顺时针方向。**

**接着 ，聪明的读者已经知道，一条线段只要两个端点在一条直线的一边（不包括边上），则线段和直线不相交，反之相交。**

**一条直线，可以平动和转动，只要满足四种情况的其中之一就可以达到题目的要求。**

![70 1][]

**只要四种极端情况满足（ 除这两个点构成的线段以外的所有线段都和该直线相交 ）这个条件，就可以输出yes了，否则输出no。**

代码如下：

int judge(Point p1,Point p2)
    {
        if(abs(p1.x-p2.x) < MIN && abs(p1.y-p2.y) < MIN)
            return 0;
        for(int i=0; i<n; i++)
            if(det(p1, p2, Left[i])*det(p1, p2, Right[i]) > MIN) return 0;//每个点都进行判断
        return 1;
    }

**总的代码在下面：**

聪明的读者已经明白

#include<iostream>
    #include<cmath>
    #include <stdio.h>
    #include <set>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    #define MAX 150
    #define MIN 1e-8
    int n;
    struct Point{
        double x, y;
    } Left[MAX], Right[MAX]; //端点存入数组
    
    double det(Point p1, Point p2, Point p3){
        return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);//判断点p3是否在线段p1p2的左右
        //  x1y2+x3y1+x2y3-x3y2-x2y1-x1y3  不要这样直接乘..可能会爆掉
    }
    
    int judge(Point p1, Point p2){
        if (abs(p1.x - p2.x) < MIN && abs(p1.y - p2.y) < MIN)
            return 0;
        for (int i = 0; i < n; i++) {
            if (det(p1, p2, Left[i]) * det(p1, p2, Right[i]) > MIN)
                return 0;//每个点都进行判断
        }
        return 1;
    }
    int main()
    {
        int T, result;
        scanf("%d", &T);
        while (T--){
            scanf("%d", &n);
            for (int i = 0; i < n; i++){
                scanf("%lf%lf%lf%lf", &Left[i].x, &Left[i].y, &Right[i].x, &Right[i].y);
            }
            result = 0;
            if (n < 3) result = true;//小于三条线段 肯定能够找到一条直线满足条件
            for (int i = 0; i < n; i++){
                for (int j = i + 1; j < n; j++) { //从i+1开始 因为之前的情况已经枚举过
                    if (result) break;
                    if (judge(Left[i], Left[j])) result = 1;
                    else if (judge(Left[i], Right[j])) result = 1;
                    else if (judge(Right[i], Left[j])) result = 1;
                    else if (judge(Right[i], Right[j])) result = 1;
                }
                if (result) break;
            }
            if (result) printf("Yes!\n");
            else printf("No!\n");
        }
        return 0;
    }

3号台风来啦，高铁要停了，赶紧想想则么回家把

我先撤了

![70 2][]

[http_poj.org_problem_id_3304]: http://poj.org/problem?id=3304
[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/31623836f8a64adb922b88a1b6ab93c4.png
[70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/34f09c8177a9421d85fd6278a64ae5b8.png
[70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d22b5523c120424b848118cb568ae2fd.png