暴力计算几何。。
#include <bits/stdc++.h> using namespace std; const double eps = 1e-10; inline int sgn(double x) { if (fabs(x) < eps) return 0; if (x < 0) return -1; return 1; } struct Point { double x, y; Point() {} Point(double x, double y): x(x), y(y) {} void input() { scanf("%lf%lf", &x, &y); } double operator^(const Point &b)const { return x * b.y - y * b.x; } double operator*(const Point &b)const { return x * b.x + y * b.y; } Point operator-(const Point &b)const { return Point(x - b.x, y - b.y); } } hole, a[15], b[15]; struct Line { Point s, e; Line() {} Line(Point s, Point e): s(s), e(e) {} int segcrossseg(Line v) { int d1 = sgn((e - s) ^ (v.s - s)); int d2 = sgn((e - s) ^ (v.e-s)); int d3 = sgn((v.e-v.s) ^ (s - v.s)); int d4 = sgn((v.e-v.s) ^ (e - v.s)); if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2; return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) || (d2 == 0 && sgn((v.e-s) * (v.e-e)) <= 0) || (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) || (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0); } } wall[15]; int n; vector<int> per; int vis[15]; inline bool gao() { memset(vis, 0, sizeof(vis)); double xx = 0, yy = 0; double nowx = 0, nowy = 0; int flagx = 0, flagy = 0; int bx = 0, by = 0; /*判断反射方向，求反射长度*/ for (int j = 0; j < (int)per.size(); ++j) { int id = per[j]; /*讨论竖直水平*/ if (sgn(wall[id].s.x - wall[id].e.x) == 0) { if (flagx == 0) { flagx = sgn(wall[id].s.x - nowx); if (sgn(wall[id].s.x - nowx) == 0 ) return 0; bx = flagx; } else { if (flagx == sgn(wall[id].s.x - nowx)) return 0; if (sgn(wall[id].s.x - nowx) == 0 ) return 0; flagx = -flagx; } xx += fabs(wall[id].s.x - nowx); nowx = wall[id].s.x; } else if (sgn(wall[id].s.y - wall[id].e.y) == 0) { if (flagy == 0) { flagy = sgn(wall[id].s.y - nowy); if (sgn(wall[id].s.y - nowy) == 0 ) return 0; by = flagy; } else { if (flagy == sgn(wall[id].s.y - nowy)) return 0; if (sgn(wall[id].s.y - nowy) == 0 ) return 0; flagy = -flagy; } yy += fabs(wall[id].s.y - nowy); nowy = wall[id].s.y; } } /*判断最后一下方向*/ if (bx == 0) bx = 1; if (by == 0) by = 1; // 默认右上角 xx += fabs(hole.x - nowx); yy += fabs(hole.y - nowy); if (sgn(hole.x - nowx) == flagx && flagx != 0) return 0; if (sgn(hole.y - nowy) == flagy && flagy != 0) return 0; // 回不到洞 /*遍历反射过程*/ double tmp = yy / xx; int tmpflag = 0; if (sgn(xx) == 0) tmpflag = 1; nowx = 0, nowy = 0; for (int j = 0; j < (int)per.size(); ++j) { int id = per[j]; if (sgn(wall[id].s.x - wall[id].e.x) == 0) { double tmpx = fabs(wall[id].s.x - nowx); double zz; if (tmpflag == 0)zz = tmpx * tmp * by; else zz = 0; Point pp(wall[id].s.x, nowy + zz); Line ll(pp, Point(nowx, nowy)); if (ll.segcrossseg(wall[id])) { vis[id] = 1; for (int i = 0 ; i < n; i++) { if (vis[i]) continue; if(ll.segcrossseg(wall[i])) return 0; } } else return 0; bx = -bx; nowx = pp.x ; nowy = pp.y; } else { double tmpy = fabs(wall[id].s.y - nowy); double zz; if (tmpflag == 0)zz = tmpy / tmp * bx; else zz = 0; Point pp(nowx + zz, wall[id].s.y); Line ll(pp, Point(nowx, nowy)); if (ll.segcrossseg(wall[id])) { vis[id] = 1; for (int i = 0 ; i < n; i++) { if (vis[i]) continue; if(ll.segcrossseg(wall[i])) return 0; } } else return 0; by = -by; nowx = pp.x ; nowy = pp.y; } } /*最后一次相交*/ double tmpx = fabs(hole.x - nowx); double tmpy = fabs(hole.y - nowy); double zz; if (tmpflag == 0)zz = tmpx * tmp * by; else zz = 0; Point pp(hole.x, nowy + zz); if (sgn(pp.y - (nowy + zz)) != 0) return 0; Line ll(pp, Point(nowx, nowy)); for (int i = 0 ; i < n; i++) { if (vis[i]) continue; if(ll.segcrossseg(wall[i])) return 0; } return 1; } inline int solve(int mask) { per.clear(); for (int i = 0; i < n; ++i) if ((mask >> i) & 1) per.push_back(i); int ret = 0; do { if (gao()) return per.size(); } while (next_permutation(per.begin(), per.end())); return -1; } int main() { scanf("%d", &n); hole.input(); for (int i = 0; i < n; ++i) { a[i].input(); b[i].input(); } if (sgn(hole.x) < 0) { for (int i = 0; i < n; ++i) { a[i].x = -a[i].x; b[i].x = -b[i].x; } hole.x = -hole.x; } if (sgn(hole.y) < 0) { for (int i = 0; i < n; ++i) { a[i].y = -a[i].y; b[i].y = -b[i].y; } hole.y = -hole.y; } for (int i = 0; i < n; ++i) wall[i] = Line(a[i], b[i]); int st = 1 << n, res = -1; for (int i = 0; i < st; ++i) res = max(res, solve(i)); if (res == -1) puts("impossible"); else printf("%d ", res); return 0; }