转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题意 ：有三个点，p0,p1,p2。有两个人alice,bob，他们初始位置为p0，现在 alice需要先到p2再到p1，bob是直接到p1。设计一条线路，使得他们初始一起走的路程尽可能地长（之后相遇不算）。要求alice走的路程和最短路之差不超过t1,bob不超过t2。
http://codeforces.com/contest/8/problem/D
题目看的一头雾水。
可以证明出最优的分离点肯定是在p0,p1,p2组成的三角形之间。
因此可以求出p0出发的角度，一旦角度确定，能走的最远路程可以通过二分求得。
同时发现当角度左右偏离，那么都只会有利于某一方，所以三分角度，二分距离。
角度可以三分p1,p2上的点。
另外还要注意一些特殊情况，如bob先到p2再到p1。沿着p1,p2行走等情况。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#define lson step<<1
#define rson step<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
struct Point{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
void input(){
scanf("%lf%lf",&x,&y);
}
}p0,p1,p2;
double t1,t2;
double sqr(double a){
return a*a;
}
double dist(Point p1,Point p2){
return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
// s->e , p at the line of s->m , s->p + p->e <= t + s->e
double solve(Point s,Point e,Point m,double t){
if(dist(s,m)+dist(m,e)<=t+dist(s,e))
return dist(s,e)+t-dist(m,e);
double low=0.0,high=1.0,mid;
for(int step=1;step<=1000;step++){
mid=(low+high)/2.0;
Point p=Point(s.x+mid*(m.x-s.x),s.y+mid*(m.y-s.y));
if(dist(s,p)+dist(p,e)<=t+dist(s,e)) low=mid;
else high=mid;
}
return mid*dist(s,m);
}
int main(){
scanf("%lf%lf",&t1,&t2);
p0.input();p1.input();p2.input();
double low=0.0,high=1.0,mid,midd,ans=0.0;
ans=max(ans,min(solve(p0,p1,p1,t2),solve(p0,p2,p1,t1)));
ans=max(ans,min(solve(p0,p1,p2,t2),solve(p0,p2,p2,t1)));
if(dist(p0,p2)+dist(p2,p1)<=t2+dist(p0,p1)){
ans=max(ans,min(dist(p0,p1)+t2,dist(p0,p2)+dist(p2,p1)+t1));
}
for(int step=1;step<=1000;step++){
mid=low+(high-low)/3.0;
midd=high-(high-low)/3.0;
Point pa=Point(p1.x+(p2.x-p1.x)*mid,p1.y+(p2.y-p1.y)*mid);
Point pb=Point(p1.x+(p2.x-p1.x)*midd,p1.y+(p2.y-p1.y)*midd);
double r1=min(solve(p0,p1,pa,t2),solve(p0,p2,pa,t1));
double r2=min(solve(p0,p1,pb,t2),solve(p0,p2,pb,t1));
if(r1>r2) high=midd,ans=max(ans,r1);
else low=mid,ans=max(ans,r2);
}
printf("%.10f\n",ans);
return 0;
}