Can anyone explain for me? Ty

Revision en1, by TooruDominateVOI, 2024-08-16 06:34:36

The problem is: On coordinate surfaces, Given N points, all vertices have integer degrees, a point P also has integer degrees located completely inside the polygon and a positive integer K. Requirement: Count the number of ways to correctly select K different vertices of the given polygon so that point P is also completely within the polygon created by the selected K vertices. Two choices are different if at least one quality is chosen in one that cannot be chosen in the other. And this is a solution a found, but I can't understand 2-pointers steps

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;

const int kMaxN = 1e5+5, kMod = 1e9+7;

int Pow(int a, int p) {
    int r = 1;
    while (p) {
        if (p & 1) {
            r = 1LL * r * a % kMod;
        }
        a = 1LL * a * a % kMod;
        p /= 2;
    }
    return r;
}

int n, k;
int fact[kMaxN], inv_fact[kMaxN];

int& Mod(int& x) {
    if (x >= kMod) {
        return x -= kMod;
    } else if (x < 0) {
        return x += kMod;
    }
    return x;
}

int Comb(int n, int k) {
    if (n < k) {
        return 0;
    }
    return 1LL * fact[n] * inv_fact[k] % kMod * inv_fact[n - k] % kMod;
}

int64 CrossProduct(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    return 1LL * a.first * b.second + 1LL * b.first * c.second + 1LL * c.first * a.second
           - 1LL * a.second * b.first - 1LL * b.second * c.first - 1LL * c.second * a.first;
}

void Init() {
    fact[0] = 1;
    for (int i = 1; i <= n; i += 1) {
        fact[i] = 1LL * fact[i - 1] * i % kMod;
    }

    for (int i = 0; i <= n; i += 1) {
        inv_fact[i] = Pow(fact[i], kMod - 2);
    }
}

int Dist(int a, int b) {
    if (b > a) {
        return b - a;
    } else {
        return b + n - a;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("poly.INP","r",stdin);
    freopen("poly.OUT","w",stdout);
    cin >> n >> k;
    Init();

    vector<pair<int, int>> points(n);
    for (auto& itr : points) {
        cin >> itr.first >> itr.second;
    }

    int answer = 0;
    int x, y; cin >> x >> y;
    int right = 1;
    for (int left = 0; left < n; left += 1) {
        while (CrossProduct(points[left], points[right], {x, y}) >= 0) {
            right += 1;
            right %= n;
        }

        int d = Dist(left, right);
        Mod(answer += Comb(d - 1, k - 1));
    }

    int a = Comb(n, k);
    Mod(a -= answer);

    cout << a << '\n';
    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English TooruDominateVOI 2024-08-16 06:34:36 2663 Initial revision (published)