Advertisement
danielvitor23

Auto Chess

Aug 3rd, 2023
1,677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5.  
  6. #define eps 1e-9
  7. #define eq(a, b) (abs(a - b) < eps)
  8. #define lt(a, b) (a < b - eps)
  9. #define gt(a, b) (a > b + eps)
  10. #define le(a, b) (a < b + eps)
  11. #define ge(a, b) (a > b - eps)
  12. #define ftype float
  13.  
  14. const ftype PI = acos(-1.0);
  15.  
  16. // Begin Point 2D
  17. struct point2d {
  18.     ftype x, y;
  19.  
  20.     point2d() : x(0.0), y(0.0) {}
  21.     point2d(const ftype& x, const ftype& y) : x(x), y(y) {}
  22.  
  23.     point2d& operator=(const point2d& oth) {
  24.         x = oth.x; y = oth.y;
  25.         return (*this);
  26.     }
  27.     point2d& operator+=(const point2d& oth) {
  28.         x += oth.x; y += oth.y;
  29.         return (*this);
  30.     }
  31.     point2d& operator-=(const point2d& oth) {
  32.         x -= oth.x; y -= oth.y;
  33.         return (*this);
  34.     }
  35.     point2d& operator*=(const ftype& factor) {
  36.         x *= factor; y *= factor;
  37.         return (*this);
  38.     }
  39.     point2d& operator/=(const ftype& factor) {
  40.         x /= factor; y /= factor;
  41.         return (*this);
  42.     }
  43. };
  44. point2d operator+(const point2d& a, const point2d& b) {
  45.     return point2d(a.x + b.x, a.y + b.y);
  46. }
  47. point2d operator-(const point2d& a, const point2d& b) {
  48.     return point2d(a.x - b.x, a.y - b.y);
  49. }
  50. point2d operator*(const point2d& a, const ftype& factor) {
  51.     return point2d(a.x * factor, a.y * factor);
  52. }
  53. point2d operator*(const ftype& factor, const point2d& a) {
  54.     return point2d(factor * a.x, factor * a.y);
  55. }
  56. point2d operator/(const point2d& a, const ftype& factor) {
  57.     return point2d(a.x / factor, a.y / factor);
  58. }
  59. bool operator==(const point2d& a, const point2d& b) {
  60.     return (eq(a.x, b.x) and eq(a.y, b.y));
  61. }
  62. bool operator!=(const point2d& a, const point2d& b) {
  63.     return !(a==b);
  64. }
  65. bool operator < (const point2d& a, const point2d& b) {
  66.     return (lt(a.x, b.x) or (eq(a.x, b.x) and lt(a.y, b.y)));
  67. }
  68. bool operator > (const point2d& a, const point2d& b) {
  69.     return (b < a);
  70. }
  71. bool operator <= (const point2d& a, const point2d& b) {
  72.     return !(a > b);
  73. }
  74. bool operator >= (const point2d& a, const point2d& b) {
  75.     return !(a < b);
  76. }
  77. // > 0 if |angle| < pi/2
  78. // = 0 if |angle| = pi
  79. // < 0 if |angle| > pi/2
  80. ftype operator*(const point2d& a, const point2d& b) {
  81.     return (a.x * b.x + a.y * b.y);
  82. }
  83. // < 0 if a comes before b in ccw
  84. // = 0 if a is collinear to b
  85. // > 0 if a comes after b in ccw
  86. ftype operator^(const point2d& a, const point2d& b) {
  87.     return (a.x * b.y - a.y * b.x);
  88. }
  89. ftype ccw(const point2d& a, const point2d& b) {
  90.     return (a ^ b);
  91. }
  92. // ccw(a, b, c) : > 0 if a comes before b counterclockwise in origin
  93. // ccw(a, b, c) : < 0 if a comes after b counterclockwise in origin
  94. ftype ccw(const point2d& a, const point2d& b, const point2d& origin) {
  95.     return ccw(a - origin, b - origin);
  96. }
  97. ftype abs(const point2d& a) {
  98.     return (a * a);
  99. }
  100. ftype norm(const point2d& a) {
  101.     return sqrt(abs(a));
  102. }
  103. ftype dist(const point2d& a, const point2d& b) {
  104.     return norm(a - b);
  105. }
  106. // Left rotation. Angle (rad)
  107. point2d rotate(const point2d& a, const ftype& angleSin, const ftype& angleCos) {
  108.     return point2d(a.x * angleCos - a.y * angleSin, a.x * angleSin + a.y * angleCos);
  109. }
  110. point2d rotate(const point2d& a, const ftype& angle) {
  111.     return rotate(a, sin(angle), cos(angle));
  112. }
  113. // 0 to 1 and 2 quadrant. 1 to 3 and 4
  114. int half(const point2d& p) {
  115.     if (gt(p.y, 0) or (eq(p.y, 0) and ge(p.x, 0))) return 0;
  116.     return 1;
  117. }
  118. // angle(a) < angle(b)
  119. bool cmpByAngle(const point2d& a, const point2d& b) {
  120.     int ha = half(a), hb = half(b);
  121.     if (ha != hb) return ha < hb;
  122.     ftype c = a^b;
  123.     if (eq(c, 0)) return lt(norm(a), norm(b));
  124.     return gt(c, 0);
  125. }
  126. // End Point 2D
  127.  
  128. const ftype angleBase = PI/4.0;
  129.  
  130. int main() {
  131.   cin.tie(0)->sync_with_stdio(0);
  132.  
  133.   int n; cin >> n;
  134.  
  135.   vector<point2d> pts(n);
  136.   for (int i = 0; i < n; ++i) {
  137.     cin >> pts[i].x >> pts[i].y;
  138.   }
  139.  
  140.   sort(pts.begin(), pts.end(), cmpByAngle);
  141.  
  142.   int ans = 0, r = 0;
  143.   for (int i = 0; i < n; ++i) {
  144.     point2d rotated = rotate(pts[i], angleBase);
  145.  
  146.     while (r < n and cmpByAngle(pts[r], rotated)) {
  147.       ++r;
  148.     }
  149.  
  150.     ans = max(ans, r - i);
  151.   }
  152.  
  153.   cout << ans << '\n';
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement