- POJ 1127
- #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;
- }
- /*
- ********
- ************
- ####....#.
- #..###.....##....
- ###.......###### ### ###
- ........... #...# #...#
- ##*####### #.#.# #.#.#
- ####*******###### #.#.# #.#.#
- ...#***.****.*###.... #...# #...#
- ....**********##..... ### ###
- ....**** *****....
- #### ####
- ###### ######
- ##############################################################
- #...#......#.##...#......#.##...#......#.##------------------#
- ###########################################------------------#
- #..#....#....##..#....#....##..#....#....#####################
- ########################################## #----------#
- #.....#......##.....#......##.....#......# #----------#
- ########################################## #----------#
- #.#..#....#..##.#..#....#..##.#..#....#..# #----------#
- ########################################## ############
- */
来源: http://www.bubuko.com/infodetail-2709091.html