Untitled
unknown
c_cpp
a year ago
2.6 kB
3
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; }; int len2(Point a, Point b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } bool cw(Point a, Point b, Point c) { return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0; } bool ccw(Point a, Point b, Point c) { return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0; } void convex_hull(vector<Point> &a) { if (a.size() == 1) return; sort(a.begin(), a.end(), [&](Point lhs, Point rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); }); Point p1 = a[0], p2 = a.back(); vector<Point> up, down; up.push_back(p1); down.push_back(p1); for (size_t i = 1; i < a.size(); i++) { if (i == a.size() - 1 || cw(p1, a[i], p2)) { while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i])) { up.pop_back(); } up.push_back(a[i]); } if (i == a.size() - 1 || ccw(p1, a[i], p2)) { while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i])) { down.pop_back(); } down.push_back(a[i]); } } a.clear(); for (size_t i = 0; i < up.size(); i++) { a.push_back(up[i]); } for (size_t i = down.size() - 2; i > 0; i--) { a.push_back(down[i]); } } 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; } convex_hull(pts); n = pts.size(); int ans = 0; for (int i = 0; i < n; i++) { int x1 = pts[i].x, y1 = pts[i].y, x2 = pts[(i + 1) % n].x, y2 = pts[(i + 1) % n].y; int a = y2 - y1; int b = x1 - x2; int c = x2 * y1 - x1 * y2; int x = ((b * b * xc) - (a * b * yc) - (a * c)) / (a * a + b * b); int y = ((a * a * yc) - (a * b * xc) - (b * c)) / (a * a + b * b); debug(x1, y1, x2, y2, x, y); if (len2({x1, y1}, {x2, y2}) > len2({x1, y1}, {x, y}) && len2({x1, y1}, {x2, y2}) > len2({x2, y2}, {x, y})) { ans++; } } cout << ans; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }