fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty