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