Advertisement
trungore10

ranking

Nov 28th, 2018
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.43 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. struct ii {
  6. int X, Y;
  7. ii() {}; ii(int X, int Y) : X(X), Y(Y) {};
  8. };
  9.  
  10. int getMul(ii a, ii b) {
  11. int tmp = (a.Y * b.Y < 0) ? -1 : 1;
  12. tmp *= (a.X*b.Y - a.Y*b.X);
  13. return (tmp < 0) ? -1 : 1;
  14. }
  15.  
  16. bool operator < (const ii a, const ii b) { return getMul(a, b) < 0; }
  17. bool operator > (const ii a, const ii b) { return getMul(a, b) > 0; }
  18. bool operator <= (const ii a, const ii b) { return getMul(a, b) <= 0; }
  19. bool operator >= (const ii a, const ii b) { return getMul(a, b) >= 0; }
  20.  
  21. const int N = 1004, oo = 1e8;
  22. int n;
  23. ii a[N];
  24.  
  25. vector<ii> lsMore, lsLess, lsEqual;
  26. int resMax, resMin;
  27.  
  28. void process(int id) {
  29. lsMore.clear(); lsLess.clear(); lsEqual.clear();
  30. for (int i = 1; i <= n; ++i) {
  31. if (i == id) continue;
  32. ii tmp = ii(a[id].Y - a[i].Y, a[id].X - a[i].X);
  33.  
  34. if (tmp.Y == 0) lsEqual.push_back(tmp);
  35. if (tmp.Y > 0) lsMore.push_back(tmp);
  36. if (tmp.Y > 0) lsLess.push_back(tmp);
  37. }
  38.  
  39. sort(lsMore.begin(), lsMore.end());
  40. sort(lsLess.begin(), lsLess.end());
  41.  
  42. int Add = 0;
  43. for (int i = 0; i < (int) lsEqual.size(); ++i) {
  44. ii frac = lsEqual[i];
  45. Add += (frac.X <= 0);
  46. }
  47.  
  48. /// all < lsMore[0] ???
  49.  
  50. lsMore.push_back(ii(oo, 1));
  51. for (int i = 0; i < (int) lsMore.size()-1; ++i) {
  52. ii frac1 = lsMore[i], frac2 = lsMore[i+1];
  53. int Lmost = lsLess.size(), Rmost = lsLess.size();
  54.  
  55. int l = 0, r = lsLess.size()-1;
  56. while (l <= r) {
  57. int mid = (l + r) / 2; ii frac = lsLess[mid];
  58. if (frac >= frac2) r = mid - 1;
  59. else if (frac < frac1) l = mid + 1;
  60. else {
  61. Rmost = mid; l = mid + 1;
  62. }
  63. }
  64.  
  65. l = 0, r = lsLess.size()-1;
  66. while (l <= r) {
  67. int mid = (l + r) / 2; ii frac = lsLess[mid];
  68. if (frac >= frac2) r = mid - 1;
  69. else if (frac < frac1) l = mid + 1;
  70. else {
  71. Lmost = mid; r = mid - 1;
  72. }
  73. }
  74.  
  75. resMax = max(resMax, i+1 + (int) lsLess.size()-1 - Lmost + 1 + Add);
  76. resMin = min(resMin, i+1 + (int) lsLess.size()-1 - Rmost + 1 + Add);
  77. }
  78. }
  79.  
  80. void sol() {
  81. for (int i = 1; i <= n; ++i) {
  82. resMax = -oo, resMin = oo;
  83. process(i);
  84. cout << n - resMax << " " << n - resMin << '\n';
  85. }
  86. }
  87.  
  88. #undef int
  89. int main() {
  90. #define int long long
  91. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  92. if (fopen("input.txt", "r")) {
  93. freopen("input.txt", "r", stdin);
  94. }
  95.  
  96. cin >> n;
  97. for (int i = 1; i <= n; ++i) cin >> a[i].X >> a[i].Y;
  98.  
  99. sol();
  100.  
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement