1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 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 142 143 144 145 146 147 148 149
|
#include <algorithm> #include <cmath> #include <cstring> using namespace std; double eps = 1e-8; const double pi = acos(-1.0); int (double x){ if(fabs(x) < eps) return 0; return (x > 0 ? 1: -1); } struct Point{ double x, y; Point(){} Point(double _x, double _y){ x = _x, y = _y; } void input(){ scanf("%lf%lf", &x, &y); } void output(){ printf("%.3lf %.3lfn", x, y); } friend bool operator == (const Point &pa, const Point &pb) { return cmp(pa.x - pb.x) == 0 && cmp(pa.y - pb.y) == 0; } friend bool operator < (const Point &pa, const Point &pb) { return cmp(pa.x - pb.x) == 0 ? cmp(pa.y - pb.y) < 0: pa.x < pb.x; } friend Point operator + (const Point &pa, const Point &pb) { return Point(pa.x + pb.x, pa.y + pb.y); } friend Point operator - (const Point &pa, const Point &pb) { return Point(pa.x - pb.x, pa.y - pb.y); } friend Point operator * (const Point &pa, const double &rat) { return Point(pa.x * rat, pa.y * rat); } friend Point operator / (const Point &pa, const double &rat) { return Point(pa.x / rat, pa.y / rat); } friend Point operator << (const Point &pa, const double &rat) { double sine = sin(rat), cosi = cos(rat); return Point(pa.x * cosi - pa.y * sine, pa.x * sine + pa.y * cosi); } friend Point operator >> (const Point &pa, const double &rat) { double sine = sin(rat), cosi = cos(rat); return Point(pa.x * cosi + pa.y * sine, pa.y * cosi - pa.x * sine); } double norm() const{ return hypot(x, y); } double sqr() const{ return x * x + y * y; } }; double dot(const Point &pa, const Point &pb) { return pa.x * pb.x + pa.y * pb.y; } double cross(const Point &pa, const Point &pb) { return pa.x * pb.y - pa.y * pb.x; } double dist(const Point &pa, const Point &pb) { return hypot(pa.x - pb.x, pa.y - pb.y); }
double rad(const Point &pa, const Point &pb){ return acos(dot(pa, pb) / (pa.norm() * pb.norm())); }
double rad(const Point &pa, const Point &pb, const Point &pc){ return acos(dot(pa - pc, pb - pc) / ((pa - pc).norm() * (pb - pc).norm())); } struct Segment{ Point s, e; Segment() {} Segment(const Point &st, const Point &ed){ if(st < ed) s = st, e = ed; else s = ed, e = st; } friend bool operator == (const Segment &sa, const Segment &sb) { return sa.s == sb.s && sa.e == sb.e; } friend double operator * (const Segment &sa, const Segment &sb) { return dot(sa.e - sa.s, sb.e - sb.s); } friend bool operator / (const Segment &sa, const Segment &sb) { return cross(sa.e - sa.s, sb.e - sb.s); } friend Point operator ^ (const Segment &sa, const Segment &sb){ double det1 = cross(sa.s - sb.s, sb.e - sb.s); double det2 = cross(sa.e - sb.s, sb.e - sb.s); return (sa.e * det1 - sa.s * det2) / (det1 - det2); } bool includes(const Point &pa) const{ return cmp(cross(pa - s, pa - e)) == 0 && cmp(dot(pa - s, pa - e)) <= 0; } bool parallel(const Segment &sa) const{ return cmp(cross(sa.e - sa.s, e - s)) == 0; } double len() const{ return dist(s, e); } }; Segment make_seg(const Point &st, const Point &ed){ return Segment(st, ed); } int n; Segment seg[15]; int con[15][15] = {0}; int main(){ while(scanf("%d", &n) == 1){ if(!n) break; for(int i = 1; i <= n; ++i){ Point p1, p2; p1.input(), p2.input(); seg[i] = make_seg(p1, p2); } for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j){ if(i == j){ con[i][j] = 1; continue; } if(seg[i].parallel(seg[j])){ if(seg[j].includes(seg[i].s) || seg[j].includes(seg[i].e)) con[i][j] = 1; }else{ Point pp = (seg[i] ^ seg[j]); if(seg[i].includes(pp) && seg[j].includes(pp)) con[i][j] = 1; } } } for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) con[i][j] |= (con[i][k] & con[k][j]); int u, v; while(scanf("%d%d", &u, &v) == 2){ if(!u && !v) break; printf("%sn", con[u][v] ? "CONNECTED" : "NOT CONNECTED"); } memset(con, 0, sizeof(con)); } return 0; }
|
近期评论