Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.6 kB
4
Indexable
#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;
}