Untitled
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; }