Advertisement
Guest User

Untitled

a guest
Mar 26th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <bits/stdc++.h> //ternary search
  2.  
  3. using namespace std;
  4.  
  5. int n;
  6. int cx[50];
  7. int cy[50];
  8. int vx[50];
  9. int vy[50];
  10. long double ans, answ;
  11.  
  12. void output(){
  13.     cout << setprecision(9) << fixed << answ;  
  14. }
  15.  
  16. void input(){
  17.     cin >> n;
  18.     for(int i = 0; i < n; i++){
  19.         cin >> cx[i];
  20.     }
  21.     for(int i = 0; i < n; i++){
  22.         cin >> cy[i];
  23.     }
  24.     for(int i = 0; i < n; i++){
  25.         cin >> vx[i];
  26.     }
  27.     for(int i = 0; i < n; i++){
  28.         cin >> vy[i];
  29.     }
  30. }
  31.  
  32. long double weight(long double t){
  33.     long double r = cx[0]+vx[0]*t;
  34.    
  35.     for(int i = 0; i < n; i++){
  36.         if(cx[i]+vx[i]*t > r){
  37.             r = cx[i]+vx[i]*t;
  38.         }
  39.     }
  40.  
  41.     long double l = cx[0]+vx[0]*t;
  42.  
  43.     for(int i = 0; i < n; i++){
  44.         if(cx[i]+vx[i]*t < l){
  45.             l = cx[i]+vx[i]*t;
  46.         }
  47.     }
  48.     return abs(r-l);
  49. }
  50.  
  51. long double high(long double t){
  52.     long double up = cy[0]+vy[0]*t;
  53.     for(int i = 0; i < n; i++){
  54.         if(cy[i]+vy[i]*t > up){
  55.             up = cy[i]+vy[i]*t;
  56.         }
  57.     }
  58.  
  59.     long double dw = cy[0]+vy[0];
  60.     for(int i = 0; i < n; i++){
  61.         if(cy[i]+vy[i]*t < dw){
  62.             dw = cy[i]+vy[i]*t;
  63.         }
  64.     }
  65.    
  66.     return abs(up-dw);
  67. }
  68.  
  69.  
  70. long double ts(){
  71.     long double l, r, mid1, mid2, hg, wg;
  72.     int tryes = 0;
  73.     l = 0;
  74.     r = 200;
  75.     while(tryes < 40){
  76.         tryes++;
  77.         mid1 = (1.0 / 3.0) * abs(weight(l) - weight(r));
  78.         mid2 = (2.0 / 3.0) * abs(weight(l) - weight(r));
  79.         if(weight(l) < mid1){
  80.             r = mid1;
  81.             continue;
  82.         }else if(weight(r) < mid2){
  83.             l = mid2;
  84.             continue;
  85.         }else{
  86.             l = mid1;
  87.             r = mid2;
  88.         }
  89.     }
  90.     cout << l << ' ' << r << endl;
  91.     wg = abs((l+r) / 2.0);
  92.     cout << wg << " ";
  93.     tryes = 0, l = 0, r = 200;
  94.     while(tryes < 40){
  95.         tryes++;
  96.         mid1 = (1.0 / 3.0) * abs(high(l) - high(r));
  97.         mid2 = (2.0 / 3.0) * abs(high(l) - high(r));
  98.         /*cout << " mid 1 = " << mid1 << " mid2 = " << mid2 << " l = " << l << " r = " << r << endl;  
  99.         */if(high(l) < mid1){
  100.             r = mid1;
  101.             continue;
  102.         }else if(high(r) < mid2){
  103.             l = mid2;
  104.             continue;
  105.         }else{
  106.             l = mid1;
  107.             r = mid2;
  108.         }
  109.     }
  110.     hg = abs((l+r) / 2.0);
  111.    
  112.     return max(hg, wg);
  113. }
  114.  
  115.  
  116. void solve(){
  117.    
  118.     ans = ts();
  119.    
  120.     /*cout << weight(2) << " " << weight(ans) << endl;
  121.     cout << high(2) << " " << high(ans) << endl;*/
  122.     answ = max(weight(ans), high(ans));
  123.    
  124. }
  125.  
  126. int main(){/*
  127.     freopen("catchthehmice.in", "r", stdin);
  128.     freopen("catchthehmice.out", "w", stdout);*/
  129.     input();
  130.     solve();
  131.     output();
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement