Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.7 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using db = long double;

constexpr db EPS = 1e-8;
constexpr db PI = 3.1415926535;

struct Point {
    int x, y;

    bool operator==(Point other) {
        return x == other.x && y == other.y;
    }

    db len2(Point p0) {
        return (x - p0.x) * (x - p0.x) + (y - p0.y) * (y - p0.y);
    }
};

db PolarAngle(Point p, Point p0) {
    return atan2(1.0 * (p.y - p0.y), 1.0 * (p.x - p0.x));
}

void solve() {
    int n, xc, yc;
    cin >> n >> xc >> yc;
    vector<Point> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }
    for (int i = 0; i < n; i++) {
        Point p0 = pts[i];
        vector<Point> srt = pts;
        sort(srt.begin(), srt.end(), [&](Point lhs, Point rhs) {
            if (fabs(PolarAngle(lhs, p0) - PolarAngle(rhs, p0)) < EPS) {
                return lhs.len2(p0) < rhs.len2(p0);
            }
            return PolarAngle(lhs, p0) < PolarAngle(rhs, p0);
        });
        int inv = 0;
        for (int i = 0; i < n; i++) {
            if (pts[i] == p0 || fabs(PolarAngle(pts[i], p0) - PolarAngle(pts[(i + 1) % n], p0)) < EPS) continue;
            while (fabs(PolarAngle(pts[i], p0) - PolarAngle(pts[(inv + 1) % n], p0)) < PI) {
                inv = (inv + 1) % n;
            }
            // inv - указатель
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}