Submission #2551845

---

Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//cout<<setprecision(20)
//cin.tie(0);
//ios::sync_with_stdio(false);
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int LBI(vector<int>&ar,int in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
int UBI(vector<int>&ar,int in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,i;cin>>n;
	vector<pair<llint,llint>>ball(n+2);
	ball[0]=mp(0,0);
	ball[1]=mp(0,0);
	for(i=0;i<n;i++){
		llint t,x;cin>>t>>x;
		ball[i+2]=mp(t,x);
	}
	lldo vmax=mod,vmin=0;
	
	for(int kai=0;kai<60;kai++){
		lldo vgen=(vmax+vmin)/2;
		lldo otL=0,otR=0;
		bool can=true;
		for(i=2;i<n+2;i++){
			bool recan=(vgen*(ball[i].fir-ball[i-1].fir)>=abs(ball[i].sec-ball[i-1].sec));
			bool otcan=(otL<=ball[i].sec+ball[i].fir*vgen)&&(ball[i].sec-ball[i].fir*vgen<=otR);
			if(recan&&otcan){
				mineq(otL,ball[i-1].sec+ball[i-1].fir*vgen);
				maxeq(otR,ball[i-1].sec-ball[i-1].fir*vgen);
			}else if(recan){}
			else if(otcan){
				otL=ball[i-1].sec+ball[i-1].fir*vgen;
				otR=ball[i-1].sec-ball[i-1].fir*vgen;
			}else{can=false;break;}
		}
		if(can){vmax=vgen;}else{vmin=vgen;}
	}
	cout<<setprecision(20)<<vmax<<endl;
	return 0;
}

Submission Info

Judge Result