Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <queue>
- #include <stack>
- #include <cstring>
- #include <map>
- #include <string>
- #include <cmath>
- using namespace std;
- double vremeist(int x1, int x2, int v1, int v2, int dir)
- {
- if(v1<=v2 && dir==0)
- return 1000000006.0;
- if(v1>=v2 && dir==1)
- return 1000000006.0;
- return (double)(x1-x2) / (v1-v2);
- }
- double vremesprotivno(int x1, int x2, int v1, int v2)
- {
- return (double)(x1-x2) / (v1+v2);
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- cout.precision(6);
- int n;
- cin>>n;
- pair<int, int> p[n+6];
- for(int i=0; i<n; i++)
- {
- cin>>p[i].first>>p[i].second;
- }
- sort(p, p+n);
- double low = 0.0;
- double high = 1000000004.2;
- double mid;
- bool f;
- int dir[n + 2];
- double maxi;
- while(fabs(low-high)>0.000001)
- {
- mid = (low+high) / 2.0;
- // cout<<fixed<<low<<"\t"<<mid<<"\t"<<high<<endl;
- dir[0] = 0;
- f = true;
- for(int i=1; i<n; i++)
- {
- if(dir[i-1]==0)
- {
- if(vremeist(p[i].first, p[i-1].first, p[i].second, p[i-1].second, 0)>=mid)
- dir[i] = 0;
- else //if(dir[i-1]==0 && vremesprotivno(p[i].first, p[i-1].first, p[i].second, p[i-1].second)>mid)
- dir[i] = 1;
- }
- else if(dir[i-1] == 1)
- {
- if(vremesprotivno(p[i].first, p[i-1].first, p[i].second, p[i-1].second)>=mid)
- dir[i] = 0;
- else if(vremeist(p[i].first, p[i-1].first, p[i].second, p[i-1].second, 1)>=mid)
- dir[i] = 1;
- else
- {
- f = false;
- break;
- }
- }
- }
- if(!f)
- {
- high = mid;
- }
- else
- {
- maxi = mid;
- low = mid;
- }
- }
- if(maxi > 1000000002.0)
- cout<<"-1"<<endl;
- else
- cout<<fixed<<maxi<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement