fork download
copy 
  1. #define __USE_MINGW_ANSI_STDIO 0
  2. #include <bits/stdc++.h>
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. using namespace std;
  8. template <class T>
  9. using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  10. template <class T>
  11. using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  12.  
  13. #define PI atan2(0, -1)
  14. #define epsilon 1e-9
  15. #define INF 5e18
  16. #define MOD 1000000007
  17.  
  18. #define mp make_pair
  19. #define pb push_back
  20. #define f first
  21. #define s second
  22. #define lb lower_bound
  23. #define ub upper_bound
  24.  
  25. int kase, N;
  26. pair<long long, long long> arr [15], mini, maxi, ret;
  27. bool ok;
  28. long long lo, hi;
  29.  
  30. void updateMini(pair<long long, long long> a){
  31.     if(mini.f == -1){
  32.         mini = a;
  33.         return;
  34.     }
  35.     if(a.f*mini.s > a.s*mini.f) mini = a;
  36. }
  37.  
  38. void updateMaxi(pair<long long, long long> a){
  39.     if(maxi.f == -1){
  40.         maxi = a;
  41.         return;
  42.     }
  43.     if(a.f*maxi.s < a.s*maxi.f) maxi = a;
  44. }
  45.  
  46. int main(){
  47.     //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
  48.     ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
  49.     cin >> kase;
  50.     for(int kk = 1; kk <= kase; kk++){
  51.         cin >> N; assert(N <= 10); mini = mp(-1, -1); maxi = mp(-1, -1); ok = true;
  52.         for(int i = 0; i < N; i++) cin >> arr[i].f >> arr[i].s;
  53.         for(int i = 0; i < N && ok; i++)
  54.             for(int j = i+1; j < N; j++){
  55.                 if(arr[j].f >= arr[i].f && arr[j].s >= arr[i].s) continue;
  56.                 if(arr[j].f <= arr[i].f && arr[j].s <= arr[i].s){ ok = false; break; }
  57.                 long long uno = arr[j].f-arr[i].f, dos = arr[i].s-arr[j].s;
  58.                 long long gg = __gcd(abs(uno), abs(dos)); uno /= gg; dos /= gg;
  59.                 if(dos > 0) updateMaxi(mp(uno, dos));
  60.                 else updateMini(mp(-uno, -dos));
  61.             }
  62.         if(!ok){
  63.             cout << "Case #" << kk << ": IMPOSSIBLE\n";
  64.             continue;
  65.         }
  66.         if(mini.f == -1) mini = mp(1, 2*MOD);
  67.         if(maxi.f == -1) maxi = mp(2*MOD, 1);
  68.         if(mini.f*maxi.s >= mini.s*maxi.f){
  69.             cout << "Case #" << kk << ": IMPOSSIBLE\n";
  70.             continue;
  71.         }
  72.         lo = 1; hi = 2*(mini.s+maxi.s); ret = mp(-1, -1);
  73.         while(lo <= hi){
  74.             long long mid = (lo+hi)/2;
  75.             long long lefty = (mini.f*mid)/mini.s+1;
  76.             long long righty = (maxi.f*mid)/maxi.s;
  77.             if((maxi.f*mid)%maxi.s == 0) righty--;
  78.             if(lefty <= righty){
  79.                 hi = mid-1;
  80.                 ret = mp(mid, lefty);
  81.             }
  82.             else lo = mid+1;
  83.         }
  84.         assert(ret != mp(-1ll, -1ll));
  85.         cout << "Case #" << kk << ": " << ret.f << ' ' << ret.s << '\n';
  86.     }
  87.     return 0;
  88. }
  89.  
  90. /******************************
  91. Kateba ii dake no hanashi darou
  92. Success is only a victory away
  93. - No Game No Life Opening
  94. ******************************/
  95.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gOO7Xn
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!