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;
}
(First I'm sorry for my bad English) Now let me explain each function first then we will go deeper to the main function
The first one is the Power Function (This function used to calculate $$$a^p$$$ in $$$O(log(p))$$$). This function use the Recursive which is:
The second function is the Init Function (Which precompute the Factorial of $$$i!$$$ modulo $$$10^9+7$$$ and the inverse Factorial of $$$i!$$$ modulo $$$10^9+7$$$). As you can see that the inverse factorial is based on the Fermat's Little Theoreom, which states that for a prime $$$p, a^{p-1} \equiv 1 (mod\ p)$$$, implying $$$a^{p-2} \equiv a^{-1} (mod\ p)$$$ and since $$$10^9-7$$$ is a prime number so we definitely can use this algorithm
The third function is the Mod Function
The fourth function is the Dist Function
The fifth function is the CrossProduct:
If you don't understand what this do well let me introduce you how to calculate the area of a triangles using the coordinates of 3 points:
We can use this to detect if a point is in a triangle (If it in the triangle then any polygon contains this triangle will definitely contains this point)
The Final function is Comb which calculates $$$C_n^k = \frac{n!}{k! \times (n-k)!}$$$ and $$$if (n < k)$$$ then return $$$0$$$ Since we have precomputed the $$$fact[n], inv\_fact[k]$$$ and the $$$inv\_fact[n-k]$$$ we can you this to compute the $$$C^k_n$$$ in $$$O(1)$$$
Ok now let's dive deeper in the main function: In the code there is a for loop like this:
Let's call $$$P(x,y)$$$ and what does the loop do is to iterate over each point in the polygon as $$$left$$$, and for each $$$left$$$, it finds the farthest $$$right$$$ such that all points from $$$left$$$ to $$$right$$$ (inclusive) lie on one side of a line defined by $$$left$$$ and a fixed point $$$P$$$. It then counts certain combinatorial configurations ($$$d - 1$$$ choose $$$k - 1$$$) and accumulates them in answer. But why we have to choose that? Well as you can see all the points of from $$$left$$$ and $$$right$$$ will certainly cannot contains the point $$$P$$$ so we have to calculate how many points like that and then at the end we calculate how many ways to choose $$$k$$$ points out of $$$n$$$ points and subtract the ways to choose k points out of $$$Dist(left, right)-1$$$ points. Therefore, the final answer is
Thanks for your clear and complete explanation, I really appreciate it!!!