[Codeforces] 782B. The Meeting Place Cannot Be Changed

題目連結:http://codeforces.com/problemset/problem/782/B

---

其實本題是對答案二分搜，驗證方法是當你把時間乘上速率後可以得到每個人最遠走到哪，看有沒有交集就知道解是否合法，不過本題有更無腦的方式，那就是對集合點模擬退火(其實是因為我當時看一眼就想到這個做法就沒去想正解了XD

#include <bits/stdc++.h>
using namespace std;
#define N 60000

double pos[N+5], speed[N+5];
int n;

inline double getY(double x);

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lf",&pos[i]);
	for(int i=0;i<n;i++)scanf("%lf",&speed[i]);
	double rr=*max_element(pos,pos+n);
	double ll=*min_element(pos,pos+n);
	default_random_engine rEng(time(NULL));
	uniform_real_distribution<double> Range(-1,1);
	uniform_real_distribution<double> expR(0,1);
	auto Random=bind(Range,rEng);
	auto expRand=bind(expR,rEng);
	int step=0;
	double pace=rr-ll, mini=0.95;
	double x=max(min(Random()*pace+ll, rr), ll), y=getY(x);
	while(pace>=1e-7){
		double newX = max(min(x + Random()*pace, rr), ll);
		double newY = getY(newX);
		if(newY < y || expRand() < exp(-step))
			x=newX, y=newY;
		step++;
		pace*=mini;
	}
	printf("%.9lf", y);
	return 0;
}

inline double getY(double x){
	double ans=-2147483647;
	for(int i=0;i<n;i++)
		ans = max(ans, abs(x-pos[i])/speed[i]);
	return ans;
}