计算几何-----》两直线是否相交

POJ1127

#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N=1000+50;
const int INF=0x3f3f3f3f;
const double EPS = 1e-10;
ll mod = 1e9+7;



//考虑误差的加法运算
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);
	}
}; 

//判断点q是否在线段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[MAX_N],q[MAX_N];
int m;
int a[MAX_N],b[MAX_N];

bool g[MAX_N][MAX_N];

void solve(){
	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];
			}
		}
	}
	
	for(int i = 0; i < m; i++){
		puts(g[a[i] - 1][b[i] - 1] ? "CONNECTED" : "NOTCONNECTED");
	} 
}

int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>p[i].x>>p[i].y>>q[i].x>>q[i].y;
	}
	solve();
	int c, d;
    while(~scanf("%d%d", &c, &d)) {
        if(c==0 && d==0)    break;
        if(g[c-1][d-1])
            printf("CONNECTED\n");
        else
            printf("NOT CONNECTED\n");
    }
 	return 0;
}

/*
                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############
*/