Submission #666159

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
const ll eps=1e-9;
vector<pair<ll,ll> > makes(ll med,ll x,ll y,ll c){
	vector<pair<ll,ll> > point;
	point.push_back(make_pair(x-med/c,y+med/c));//左上
	point.push_back(make_pair(x+med/c,y+med/c));//右上
	point.push_back(make_pair(x-med/c,y-med/c));//左下
	point.push_back(make_pair(x+med/c,y-med/c));//右下
	return point;
}
int main(){
	ll n;	cin>>n;
	vector<ll> x(n),y(n),c(n);
	for(int i=0;i<n;i++)	cin>>x[i]>>y[i]>>c[i];
	ll left=0,right=1e9;
	for(int t=0;t<100;t++){
		ll med=(left+right)/2;//行ける秒数
		vector<pair<ll,ll> > point=makes(med,x[0],y[0],c[0]);
		bool failed=false;
		for(int i=1;i<n;i++){
			vector<pair<ll,ll> > p=makes(med,x[i],y[i],c[i]);
			//範囲よりも左にある
			if(point[0].first-p[3].first>-eps)	failed=true;
			//上にある
			else if(p[3].second-point[0].second>-eps)	failed=true;
			//右
			else if(p[0].first-point[3].first>-eps)	failed=true;
			//下
			else if(point[3].second-p[0].second>-eps)	failed=true;
			if(failed)	break;
			if(p[0].first-point[0].first>-eps){//左の確認
				point[0].first=p[0].first;
				point[2].first=p[2].first;
			}
			if(point[0].second-p[0].second>-eps){//上
				point[0].second=p[0].second;
				point[1].second=p[0].second;
			}
			if(point[3].first-p[3].first>-eps){//右
				point[3].first=p[3].first;
				point[1].first=p[1].first;
			}
			if(p[3].second-point[3].second>-eps){//下
				point[3].second=p[3].second;
				point[2].second=p[2].second;
			}
		}
		if(failed)	left=med;
		else right=med;
	}
	printf("%.15Lf",left);
	return 0;
}

Submission Info

Judge Result