POJ 1127 Jack Straws （计算几何）

Description

Input

Output

Sample Input

7
1 6 3 3 
4 6 4 9 
4 5 6 7 
1 4 3 5 
3 5 5 5 
5 2 6 3 
5 4 7 2 
1 4 
1 6 
3 3 
6 7 
2 3 
1 3 
0 0

2
0 2 0 0
0 0 0 1
1 1
2 2
1 2
0 0

0

Sample Output

CONNECTED 
NOT CONNECTED 
CONNECTED 
CONNECTED 
NOT CONNECTED 
CONNECTED
CONNECTED
CONNECTED
CONNECTED

题意：

桌子上放着n根木棍，木棍的两端坐标分别是(Pix, Piy)和(Qix, Qiy)。给定m对木棍(ai, bi),请判断没对木棍是否相连。当两根木棍之间有公共点时，就认为它们是相连的。通过相连的木棍间接的连在一起的两根木棍也认为是相连的。

分析：

木棍就是二维平面上的线段，只有能够判断线段是否相交，那么建图以后就可以轻松的进行连接性判断。那么，应该如何判断两条线段是否相交呢？首先会想到计算两直线的交点，然后判断交点是否在线段上这一方法。那么两条直线的交点要怎么求得呢？虽然可以把直线表示成方程，通过联立方程组求解，但是在几何问题中，运用向量的内积和外积进行计算是非常方便的。对于二维向量p1=(x1, y1) 和 p2=(x2, y2)，我们定义内积p1*p2 = x1x2 +y1y2，外积p1*p2 = x1y2 – x2y1。要判断点q是否在线段p1-p2上，只有先利用外积根据是否有(p1-q)*(p2 – q)=0来判断点q是否在直线p1-p2上，在利用内积根据是否有(p1-q)*(p2– q)<=0来判断点q是否落在p1-p2之间。而要求两直线的交点，通过变量t将直线p1-p2上的点表示为p1+t(p2-p1)，交点又在直线q1-q2上，所以有：

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

于是可以利用下式求得t的值

P1+(q2-q1)*(q1-p1)*(p2-p1)/(q2-q1)*(p2-p1)

但是，使用这个方法时还有注意边界情况。让我们来看看样例中的木棍2和木棍4，这两条线段是平行的，对应直线没有交点。但平行的线段也可能有公共点，所有此时需要特别注意。对此有不同的处理方法，这里我们选择通过检查端点是否在另一条线段上来判断。

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
double EPS = 1e-10;

//考虑误差的加法运算
double add(double a, double b)
{
    if (abs(a + b) < EPS * (abs(a) + abs(b)))
        return 0;
    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);
    }
};

//判断dianq是否在线段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 n;
P p[15], q[15];
int m;
int a, b;
bool g[15][15];    //相连关系图

void solve()
{
    memset(g, false, sizeof(g));
    for (int i = 0; i < n; i++){
        g[i][i] = true;
        for (int j = 0; j < i; j++){
            //判断木棍i和木棍j是否有公共点
            if ((p[i] - q[i]).det(p[j] - q[j]) == 0){
                //平行时
                g[i][j] = g[j][i] = on_seg(p[i], q[i], p[j])
                                 || on_seg(p[i], q[i], q[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]);
                g[i][j] = g[j][i] = on_seg(p[i], q[i], r) && on_seg(p[j], q[j], r);
            }
        }
    }
    //通过Floyd-Warshall算法判断任意两点间是否相连
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                g[i][j] |= g[i][k] && g[k][j];
            }
        }
    }
    while (scanf("%d%d", &a, &b) != EOF){
        if (a == 0 && b == 0){
            break;
        }
        puts(g[a - 1][b - 1] ? "CONNECTED" : "NOT CONNECTED");
    }
}

int main()
{
    while (scanf("%d", &n), n){
        for (int i = 0; i < n; i++){
            scanf("%lf%lf%lf%lf", &p[i].x, &p[i].y, &q[i].x, &q[i].y);
        }
        solve();
    }
    return 0;
}

POJ 1127 Jack Straws （计算几何）

原文：http://blog.csdn.net/a2459956664/article/details/51416665