Guest User

Untitled

a guest
Apr 24th, 2018
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef int ll;
  6. typedef double dbl;
  7. #define fr(x,a,b) for(ll x=a;x<b;x++)
  8. #define rf(x,a,b) for(ll x=a;x>=b;x--)
  9. #define pii pair<ll,ll>
  10. #define PB push_back
  11. #define MP make_pair
  12. #define mod 1000000007
  13. #define gmax LLONG_MAX
  14. #define gmin LLONG_MIN
  15. #define INF 2e9
  16. #define N 101
  17. #define MAX(a,b,c,d) max(a,max(b,max(c,d)))
  18. #define MIN(a,b,c) min(min(a,b),c)
  19. #define SZ(s) s.size()
  20. #define MS(x,v) memset(x,v,sizeof(x))
  21.  
  22. struct Child{
  23. ll x,v;
  24. };
  25.  
  26. bool cmp(Child c1,Child c2){
  27. return c1.x<c2.x;
  28. }
  29.  
  30. ll n;
  31. Child c[N];
  32.  
  33. bool possible(dbl t){
  34. ll dir=0;
  35.  
  36. fr(i,1,n){
  37. // direction of (i-1) is RHS
  38. if(dir){
  39. if((dbl)(c[i].x-c[i-1].x)/(dbl)(c[i].v+c[i-1].v)>t) dir=0; // assigning LHS direction to (i)
  40. else if((dbl)(c[i].x-c[i-1].x)/(dbl)abs((c[i].v-c[i-1].v))>t) dir=1; // assigning RHS direction to (i)
  41. else if(c[i-1].v<=c[i].v) dir=1; // assigning RHS direction to (i)
  42. else return false; // no direction assignment possible to (i)
  43. }
  44.  
  45. // direction of (i-1) is LHS
  46. else{
  47. if((dbl)(c[i].x-c[i-1].x)/(dbl)(c[i].v-c[i-1].v)>t) dir=0; // assigning LHS direction to (i)
  48. else if(c[i].v<=c[i-1].v) dir=0; // assigning LHS direction to (i)
  49. else dir=1; // assigning RHS direction to (i)
  50. }
  51. }
  52.  
  53. return true;
  54. }
  55.  
  56. int main(){
  57. ios::sync_with_stdio(false);
  58. cin.tie(NULL);
  59. cout.tie(NULL);
  60. ll t;
  61. cin>>t;
  62.  
  63. while(t--){
  64. cin>>n;
  65.  
  66. fr(i,0,n) cin>>c[i].x>>c[i].v;
  67.  
  68. sort(c,c+1,cmp);
  69.  
  70. dbl left=0,right=1e20,mid;
  71.  
  72. while(right-left>=1e-6){
  73. mid=(left+right)*0.5;
  74. if(possible(mid)) left=mid;
  75. else right=mid;
  76. }
  77.  
  78. if(mid>1e15) cout<<-1<<"\n";
  79. else cout<<fixed<<setprecision(6)<<mid<<"\n";
  80. }
  81.  
  82. return 0;
  83. }
Add Comment
Please, Sign In to add comment