Advertisement
achulkov2

Untitled

Jun 19th, 2018
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. using C = int;
  9. using M = long long;
  10.  
  11. struct Vec {
  12.     C x, y;
  13.     explicit Vec(C x = 0, C y = 0): x(x), y(y) {}
  14.     Vec operator + (const Vec &v) const {
  15.         return Vec(x + v.x, y + v.y);
  16.     }
  17.     Vec operator - (const Vec &v) const {
  18.         return Vec(x - v.x, y - v.y);
  19.     }
  20.     M operator * (const Vec& v) const {
  21.         return static_cast<M>(x) * v.x + static_cast<M>(y) * v.y;
  22.     }
  23.     M operator % (const Vec &v) const {
  24.         return static_cast<M>(x) * v.y - static_cast<M>(y) * v.x;
  25.     }
  26. };
  27.  
  28. using ld = long double;
  29. const ld TAU = 2 * atan2(0, -1);
  30.  
  31. // Angle in [0, TAU)
  32. ld angle(const Vec& p) {
  33.     ld ang = atan2(p.y, p.x);
  34.     return (ang < 0 ? TAU + ang : ang);
  35. }
  36.  
  37. ld find_best_angle(const vector<Vec>& points, ld a) {
  38.     if (a > TAU) {
  39.         return 0;
  40.     }
  41.     vector<ld> pa;
  42.     for (const auto& p : points) {
  43.         auto ang = angle(p);
  44.         pa.push_back(ang);
  45.         pa.push_back(ang + TAU);
  46.     }
  47.     sort(pa.begin(), pa.end());
  48.     int mx = -1;
  49.     ld ans = 0;
  50.     for (size_t i = 0; i < points.size(); ++i) {
  51.         int cnt = (upper_bound(pa.begin(), pa.end(), pa[i] + a) - pa.begin()) - i;
  52.         if (cnt > mx) {
  53.             mx = cnt;
  54.             ans = pa[i];
  55.         }
  56.     }
  57.     return ans;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement