SPOJ AMR12C Entmoot（二分+圆的面积交）
题意是有n个人，每个人有各自坐标以及速度，求一个点X，使得所有点走到X点，耗时最大的那个人的耗时最小。输出这个时间。
抽象成圆的面积交： 二分枚举时间将求极值问题转换为判定问题。如何判断是否存在一个点X，使得所有点都能在time时间内到达X？ 每个人在time时间内的运动范围是以其初始座标为圆心，半径 v*time的一个圆。那么问题就很直观了，只要由time生成的这n个圆存在交，那么所有人就能在time时间内走到一起了。
不过悲剧的是我没有圆面积交的模板。。。所以只能换一种方法求圆的面积交：是否存在一个区域（任意规则），这个区域中有一个点在所有圆内？显然如果存在这样一个点，n个圆就有公共交了。
具体求法：求出所有圆的交点，然后对于一个圆上所有的交点极角排序，如果连续两个交点的中间点能被“看见”，那么着这段弧所在的“区域”也就是“可见”的了。也就意味着当前time可解。
#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<cstdlib>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define MP make_pairusing namespace std;const double eps = 1e-8;const double PI = acos(-1.0);const double TWO_PI = 2*PI;int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;}//将角度标准化double NormalizeAngle(double rad, double center = PI) { return rad - TWO_PI * floor((rad + PI - center) / TWO_PI);}struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { }};typedef Point Vector;Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y);}bool operator == (const Point& a, const Point &b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;}double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }double Length(Vector A) { return sqrt(Dot(A, A)); }double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }double angle(Vector v) { return atan2(v.y, v.x); }double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }Vector vecunit(Vector x){ return x / Length(x);} //单位向量Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x);} //垂直法向量Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));}double Area2(const Point A, const Point B, const Point C) { return Length(Cross(B-A, C-A)); }// 交点相对于圆1的极角保存在rad中void getCircleCircleIntersection(Point c1, double r1, Point c2, double r2, vector<double>& rad) { double d = Length(c1 - c2); if(dcmp(d) == 0) return; // 不管是内含还是重合，都不相交 if(dcmp(r1 + r2 - d) < 0) return; if(dcmp(fabs(r1-r2) - d) > 0) return; double a = angle(c2 - c1); double da = acos((r1*r1 + d*d - r2*r2) / (2*r1*d)); rad.push_back(NormalizeAngle(a-da)); rad.push_back(NormalizeAngle(a+da));}const int maxn = 200;int n, T;Point p[maxn];double s[maxn], R[maxn];//一个点是否能被所有圆 “看见”inline bool all(Point a){ REP(i, n) if(Length(p[i] - a) > R[i]) return false; return true;}inline bool check(vector<double> sol, Point p, double r){ sort(sol.begin(), sol.end()); REP(i, sol.size()-1) if(sol[i+1] - sol[i] > eps) { //该圆弧的中点 double mid = (sol[i] + sol[i+1]) / 2; //圆弧上的点，往圆内或者圆外走一点 //貌似不加这个会wa。。。 for(int side = -1; side <= 1; side += 2) { double r2 = r - side*eps; Point a = Point(p.x + cos(mid)*r2, p.y + sin(mid)*r2); if(all(a)) return true; } } return false;}inline bool ok(double m){ //构造圆 REP(i, n) R[i] = s[i]*m; REP(i, n) { //枚举每个圆上的所有弧 vector<double> rad; //初始圆的弧是 0~2*PI rad.PB(0); rad.PB(2*PI); REP(j, n) if(i != j) getCircleCircleIntersection(p[i], R[i], p[j], R[j], rad); if(check(rad, p[i], R[i])) return true; } return false;}int main(){ scanf("%d", &T); while(T--) { scanf("%d", &n); REP(i, n) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &s[i]); double L=0, R=1e7, M; while(L + eps < R) { M = (L + R) / 2; if(ok(M)) R = M; else L = M; } printf("%.4lf\n", L); } return 0;}