平面几何

模板

const double eps=1e-10;
//考虑就误差的加法
double add(double a , double b){
    if(fabs(a+b) < eps * ( fabs(a)+fabs(b) ) ) return 0;
    return a + b;
}
struct P{
    double x,y;
    P (){ }
    P (double a, double b):x(a),y(b){}
    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);
    }
};
bool on_seg(P p1,P p2 ,P q){//判断q点是否在线段(p1-p2)上 
    return (p1 - q).det(p2 - q)==0 && (p1 -q).dot(p2 - q) <= 0;
}
P intersection(P p1, P p2 ,P q1 , P q2){//计算直线(p1-p2)与(q1-q2)的
    return p1 +  (p2 - p1)*((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}
bool parallel(P p1 , P p2 , P q1 , P q2){//判断(p1-p2)和(q1-q2)是否平行，平行返回1
    return (p1-p2).det(q1-q2)==0? 1 : 0 ;
}
P ps[NV];
//字典序比较
bool cmp_x(const P &p , const P &q){
    if(p.x!=q.x)return p.x < q.x;
    return p.y < q.y;
}
double dist(P p, P q){
    return (p-q).dot(p-q);
}

POJ_1127

题意

现在平面上有n条线段，任意选择上面两条线段，看其能否连通。

c++代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const double eps=1e-10;
//考虑就误差的加法
double add(double a , double b){
    if(fabs(a+b) < eps * ( fabs(a)+fabs(b) ) ) return 0;
    return a + b;
}
struct P{
    double x,y;
    P (){ }
    P (double a, double b):x(a),y(b){}
    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);
    }
};
bool on_seg(P p1,P p2 ,P q){//判断q点是否在线段(p1-p2)上 
    return (p1 - q).det(p2 - q)==0 && (p1 -q).dot(p2 - q) <= 0;
}
P intersection(P p1, P p2 ,P q1 , P q2){//计算直线(p1-p2)与(q1-q2)的
    return p1 +  (p2 - p1)*((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}
bool parallel(P p1 , P p2 , P q1 , P q2){//判断(p1-p2)和(q1-q2)是否平行，平行返回1
    return (p1-p2).det(q1-q2)==0? 1 : 0 ;
}
int n;
bool g[20][20];
P p[20],q[20];
void solve(){
    for (int i = 0 ; i < n ; i++ ){
        g[i][i]=1;
        for(int j= 0 ; j < i ; j++){
            if(parallel(p[i],q[i],p[j],q[j])){
                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);
            }
        }
    }
    for(int k = 0 ; k < n ; k++){
        //(i-j)两点能否通过点k相连通
        for(int i =0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                g[i][j] |= g[i][k]&&g[k][j];
            }
        }
    }
}
void init(){
    memset(g,0,sizeof(g));
    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();
}
int main()
{   
    while(cin>>n){
        if(n==0)break;
        init();
        int a,b;
        while(scanf("%d%d",&a,&b)){
            if(a==0 && b==0)break;
            puts(g[a-1][b-1]?"CONNECTED":"NOT CONNECTED");
        }
    }
    
    return 0;
}