本文共 3416 字，大约阅读时间需要 11 分钟。
POJ 1127
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define pi acos(-1) 13 #define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 14 using namespace std; 15 typedef long long ll; 16 const int MAX_N=1000+50; 17 const int INF=0x3f3f3f3f; 18 const double EPS = 1e-10; 19 ll mod = 1e9+7; 20 21 22 23 //考虑误差的加法运算 24 double add(double a,double b){ 25 if(abs(a + b) < EPS * (abs(a) + abs(b))) return 0; 26 return a+ b; 27 } 28 29 //二维向量结构体 30 struct P{ 31 double x,y; 32 P(){} 33 P(double x, double y) : x(x), y(y){ 34 } 35 P operator + (P p){ 36 return P(add(x, p.x), add(y, p.y)); 37 } 38 P operator - (P p){ 39 return P(add(x, -p.x), add(y, -p.y)); 40 } 41 P operator * (double d){ 42 return P(x * d, y * d); 43 } 44 double dot(P p){ //内积 45 return add(x * p.x, y * p.y); 46 } 47 double det(P p){ //外积 48 return add(x * p.y, -y * p.x); 49 } 50 }; 51 52 //判断点q是否在线段p1-p2上 53 bool on_seg(P p1, P p2, P q){ 54 return (p1 - q).det(p2-q) == 0 && (p1 - q).dot(p2 - q) <= 0; 55 } 56 57 //计算直线p1-p2与直线q1-q2的交点 58 P intersection(P p1, P p2, P q1, P q2){ 59 return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1)); 60 } 61 62 int n; 63 P p[MAX_N],q[MAX_N]; 64 int m; 65 int a[MAX_N],b[MAX_N]; 66 67 bool g[MAX_N][MAX_N]; 68 69 void solve(){ 70 for(int i = 0; i < n; i++){ 71 g[i][i] = true; 72 for(int j = 0; j < i; j++){ 73 //判断木棍i和木棍j是否有公共点 74 if((p[i] - q[i]).det(p[j] - q[j]) == 0){ 75 //平行时 76 g[i][j] = g[j][i] = on_seg(p[i], q[i], p[j]) 77 || on_seg(p[i], q[i], q[j]) 78 || on_seg(p[j], q[j], p[i]) 79 || on_seg(p[j], q[j], q[i]); 80 }else{ 81 //非平行时 82 P r = intersection(p[i], q[i], p[j], q[j]); 83 g[i][j] = g[j][i] = on_seg(p[i], q[i], r) && on_seg(p[j],q[j],r); 84 } 85 } 86 } 87 //通过Floyd_Warshall算法判断任意两点间是否相连 88 for(int k = 0; k < n; k++){ 89 for(int i = 0; i< n; i++){ 90 for(int j = 0; j < n; j++){ 91 g[i][j] |= g[i][k] && g[k][j]; 92 } 93 } 94 } 95 96 for(int i = 0; i < m; i++){ 97 puts(g[a[i] - 1][b[i] - 1] ? "CONNECTED" : "NOTCONNECTED"); 98 } 99 }100 101 int main(){102 cin>>n;103 for(int i = 0; i < n; i++){104 cin>>p[i].x>>p[i].y>>q[i].x>>q[i].y;105 }106 solve();107 int c, d;108 while(~scanf("%d%d", &c, &d)) {109 if(c==0 && d==0) break;110 if(g[c-1][d-1])111 printf("CONNECTED\n");112 else113 printf("NOT CONNECTED\n");114 }115 return 0;116 }117 118 /*119 ********120 ************121 ####....#.122 #..###.....##....123 ###.......###### ### ###124 ........... #...# #...#125 ##*####### #.#.# #.#.#126 ####*******###### #.#.# #.#.#127 ...#***.****.*###.... #...# #...#128 ....**********##..... ### ###129 ....**** *****....130 #### ####131 ###### ######132 ##############################################################133 #...#......#.##...#......#.##...#......#.##------------------#134 ###########################################------------------#135 #..#....#....##..#....#....##..#....#....#####################136 ########################################## #----------#137 #.....#......##.....#......##.....#......# #----------#138 ########################################## #----------#139 #.#..#....#..##.#..#....#..##.#..#....#..# #----------#140 ########################################## ############141 */
转载于:https://www.cnblogs.com/Yinchen-One/p/9399449.html