(POJ) 1127 -- Jack Straws [點的操作]

http://poj.org/problem?id=1127

裡面有一些有關點的操作

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX_N = 15;
const double eps = 1e-9;

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+(const P p1,const P p2) {
    return P(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P p1,const P p2) {
    return P(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const P p1,const double d) {
    return P(p1.x*d,p1.y*d);
}

double dot(const P p1,const P p2) {
    return add(p1.x*p2.x , p1.y*p2.y);
}

double cross(const P p1,const P p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

bool on_seg(P p1,P p2,P q) {
    return cross(p1-q,p2-q) == 0 && dot(p1-q,p2-q)<=0;
}

P touch(P p1,P p2,P q1,P q2) {
    return p1 + (p2-p1)*(cross(q1-p1,q2-q1)/cross(p2-p1,q2-q1));
}

bool dp[MAX_N][MAX_N];
P p[MAX_N],q[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        for (int x=1;n>=x;x++) {
            double a,b,c,d;
            scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
            p[x] = P(a,b);
            q[x] = P(c,d);
        }
        for (int x=0;n>=x;x++) {
            for (int y=0;n>=y;y++) {
                dp[x][y] = false;
                if (x==y) dp[x][y]=true;
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=i+1;n>=j;j++) {
                bool ans=false;
                if (cross(p[i]-q[i],p[j]-q[j])==0) {  //pararell
                    ans |= on_seg(p[i],q[i],p[j]) || on_seg(p[i],q[i],q[j]);
                    ans |= on_seg(p[j],q[j],p[i]) || on_seg(p[j],q[j],q[i]);
                }
                else {
                    P ret=touch(p[i],q[i],p[j],q[j]);
                    ans = on_seg(p[i],q[i],ret) && on_seg(p[j],q[j],ret);
                }
                dp[i][j] = dp[j][i] = ans;
            }
        }
        for (int k=1;n>=k;k++) {
            for (int i=1;n>=i;i++) {
                for (int j=1;n>=j;j++) {
                    dp[i][j] = dp[i][j] || dp[i][k] && dp[k][j];
                }
            }
        }
        int a,b;
        while (scanf("%d %d",&a,&b) != EOF) {
            if (!a && !b) break;
            else {
                if (dp[a][b]) puts("CONNECTED");
                else puts("NOT CONNECTED");
            }
        }
    }
}