欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-02 10:06:14
...

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;
}

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