水题了，发现不了错误的话看看输入有没有问题
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 100; const double eps = 1e-10; int dcmp(double x) { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } struct Point { double x, y; Point(double xx = 0, double yy = 0) : x(xx), y(yy) {} Point operator + (Point p) const { return Point(x+p.x, y+p.y); } Point operator - (Point p) const { return Point(x-p.x, y-p.y); } Point operator * (double d) const { return Point(x*d, y*d); } double dot(Point p) { return x*p.x+y*p.y; } double det(Point p) { return x*p.y-y*p.x; } }; bool onseg(Point p1, Point p2, Point q) { return dcmp((p1-q).det(p2-q)) == 0 && dcmp((p1-q).dot(p2-q)) <= 0; } Point intersection(Point p1, Point p2, Point q1, Point q2) { return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1)); } int n; Point p[maxn], q[maxn]; int g[maxn][maxn]; void solve() { memset(g, 0, sizeof(g)); for (int i = 0; i < n; i++) g[i][i] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (dcmp((p[i]-q[i]).det(p[j]-q[j])) == 0) { g[i][j] = g[j][i] = onseg(p[i], q[i], p[j]) || onseg(p[i], q[i], q[j]) || onseg(p[j], q[j], p[i]) || onseg(p[j], q[j], q[i]); } else { Point r = intersection(p[i], q[i], p[j], q[j]); g[i][j] = g[j][i] = onseg(p[i], q[i], r) && onseg(p[j], q[j], r); } } } 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]; } } } int a, b; while (scanf("%d%d", &a, &b) != EOF) { if (a == 0 && b == 0) break; puts(g[a - 1][b - 1] ? "CONNECTED" : "NOT CONNECTED"); } } int main() { while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) scanf("%lf %lf %lf %lf", &p[i].x, &p[i].y, &q[i].x, &q[i].y); solve(); } return 0; }