Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- using C = int;
- using M = long long;
- struct Vec {
- C x, y;
- explicit Vec(C x = 0, C y = 0): x(x), y(y) {}
- Vec operator + (const Vec &v) const {
- return Vec(x + v.x, y + v.y);
- }
- Vec operator - (const Vec &v) const {
- return Vec(x - v.x, y - v.y);
- }
- M operator * (const Vec& v) const {
- return static_cast<M>(x) * v.x + static_cast<M>(y) * v.y;
- }
- M operator % (const Vec &v) const {
- return static_cast<M>(x) * v.y - static_cast<M>(y) * v.x;
- }
- };
- using ld = long double;
- const ld TAU = 2 * atan2(0, -1);
- // Angle in [0, TAU)
- ld angle(const Vec& p) {
- ld ang = atan2(p.y, p.x);
- return (ang < 0 ? TAU + ang : ang);
- }
- ld find_best_angle(const vector<Vec>& points, ld a) {
- if (a > TAU) {
- return 0;
- }
- vector<ld> pa;
- for (const auto& p : points) {
- auto ang = angle(p);
- pa.push_back(ang);
- pa.push_back(ang + TAU);
- }
- sort(pa.begin(), pa.end());
- int mx = -1;
- ld ans = 0;
- for (size_t i = 0; i < points.size(); ++i) {
- int cnt = (upper_bound(pa.begin(), pa.end(), pa[i] + a) - pa.begin()) - i;
- if (cnt > mx) {
- mx = cnt;
- ans = pa[i];
- }
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement