CF 8D Two Friends (三分+二分)

題意 ：有三個點，p0,p1,p2。有兩個人alice,bob，他們初始位置為p0，現在 alice需要先到p2再到p1，bob是直接到p1。設計一條線路，使得他們初始一起走的路程盡可能地長（之後相遇不算）。要求alice走的路程和最短路之差不超過t1,bob不超過t2。       題目看的一頭霧水。   可以證明出最優的分離點肯定是在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;
}