挺水的一道题，直接二分圆的半径即可。1y~
类似于以前半平面交求核的做法，假设半径已经知道，我们只需要求出线段周围哪些位置是不能放置圆心的即可。这样就转换为圆与直线，直线与直线交的问题了。
不知道这题能不能SAA过，有空试下。
代码如下：
1 #include <cmath> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 8 using namespace std; 9 10 const double EPS = 1e-5; 11 inline int sgn(double x) { return (x > EPS) - (x < -EPS);} 12 typedef pair<double, double> Point; 13 #define x first 14 #define y second 15 template<class T> T sqr(T x) { return x * x;} 16 Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y);} 17 Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);} 18 Point operator * (Point a, double p) { return Point(a.x * p, a.y * p);} 19 Point operator / (Point a, double p) { return Point(a.x / p, a.y / p);} 20 21 inline double cross(Point a, Point b) { return a.x * b.y - a.y * b.x;} 22 inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y;} 23 inline double veclen(Point a) { return sqrt(dot(a, a));} 24 inline Point vecunit(Point a) { return a / veclen(a);} 25 inline Point normal(Point a) { return Point(-a.y, a.x) / veclen(a);} 26 27 struct Line { 28 Point s, t; 29 Line() {} 30 Line(Point s, Point t) : s(s), t(t) {} 31 Point vec() { return t - s;} 32 Point point(double p) { return s + vec() * p;} 33 Line move(double p) { // + left - right 34 Point nor = normal(vec()); 35 return Line(s + nor * p, t + nor * p); 36 } 37 } ; 38 39 inline bool between(Point o, Point a, Point b) { return sgn(dot(a - o, b - o)) < 0;} 40 inline bool between(Point a, Line l) { return between(a, l.s, l.t);} 41 inline Point llint(Line a, Line b) { return a.point(cross(b.vec(), a.s - b.s) / cross(a.vec(), b.vec()));} 42 43 bool clint(Point a, double r, double *sol) { 44 if (sgn(r - fabs(a.y)) <= 0) return 0; 45 double d = sqrt(sqr(r) - sqr(a.y)); 46 //cout << "d " << d << endl; 47 sol[0] = a.x - d; 48 sol[1] = a.x + d; 49 return 1; 50 } 51 52 Line Y0 = Line(Point(0, 0), Point(1, 0)); 53 54 double L; 55 inline void adjust(double &x) { x = max(0.0, min(L, x));} 56 Point getseg(Line a, double r) { 57 vector<double> sol; 58 sol.clear(); 59 double t[2]; 60 if (clint(a.s, r, t)) sol.push_back(t[0]), sol.push_back(t[1]); 61 if (clint(a.t, r, t)) sol.push_back(t[0]), sol.push_back(t[1]); 62 Line l1 = a.move(r), l2 = a.move(-r), l3 = Line(l1.s, l2.s), l4 = Line(l1.t, l2.t); 63 Point p1 = llint(l1, Y0), p2 = llint(l2, Y0), p3 = llint(l3, Y0), p4 = llint(l4, Y0); 64 if (between(p1, l1)) sol.push_back(p1.x); 65 if (between(p2, l2)) sol.push_back(p2.x); 66 if (between(p3, l3)) sol.push_back(p3.x); 67 if (between(p4, l4)) sol.push_back(p4.x); 68 if (sol.size() == 0) return Point(-1, -1); 69 sort(sol.begin(), sol.end()); 70 //cout << "sol "; 71 //for (int i = 0; i < sol.size(); i++) cout << sol[i] << ' '; cout << endl; 72 adjust(sol[0]), adjust(sol[sol.size() - 1]); 73 return Point(sol[0], sol[sol.size() - 1]); 74 } 75 76 const int N = 2222; 77 typedef pair<double, int> Event; 78 Line l[N]; 79 int n; 80 81 bool test(double r) { 82 vector<Event> ev; 83 ev.clear(); 84 for (int i = 0; i < n; i++) { 85 Point tmp = getseg(l[i], r); 86 if (tmp.x < 0 || tmp.y < 0) continue; 87 //cout << tmp.x << '~' << tmp.y << endl; 88 ev.push_back(Event(tmp.x, 1)); 89 ev.push_back(Event(tmp.y, -1)); 90 } 91 sort(ev.begin(), ev.end()); 92 //cout << r << endl; 93 //for (int i = 0; i < ev.size(); i++) cout << ev[i].x << '&' << ev[i].y << ' '; cout << endl; 94 double last = 0; 95 int cnt = 0, sz = ev.size(); 96 for (int i = 0; i < sz; i++) { 97 if (ev[i].y == 1) { 98 if (cnt == 0 && sgn(ev[i].x - last) > 0) return 1; 99 cnt++; 100 } else { 101 if (cnt == 1) last = ev[i].x; 102 cnt--; 103 } 104 } 105 return sgn(L - last) > 0; 106 } 107 108 int main() { 109 //freopen("in", "r", stdin); 110 int T; 111 cin >> T; 112 while (T-- && cin >> n >> L) { 113 for (int i = 0; i < n; i++) cin >> l[i].s.x >> l[i].s.y >> l[i].t.x >> l[i].t.y; 114 double lp = 0, rp = 222222, mp; 115 while (rp - lp > EPS) { 116 mp = (lp + rp) / 2; 117 if (test(mp)) lp = mp; 118 else rp = mp; 119 } 120 //puts("~~~~~~~~~~~~~~~~~~~~~~~~"); 121 //test(2.118); 122 printf("%.3f ", mp); 123 } 124 return 0; 125 }
——written by Lyon