TooruQuyetCoVOI's blog

By TooruQuyetCoVOI, history, 3 weeks ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

(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:

$$$ \text{Pow}(a, p) = \begin{cases} 1, & \text{if } p = 0 \\ (a^{\frac{p}{2}} \mod kMod) \times (a^{\frac{p}{2}} \mod kMod) \times a, & \text{if } p \text{ is odd} \\ (a^{\frac{p}{2}} \mod kMod) \times (a^{\frac{p}{2}} \mod kMod), & \text{if } p \text{ is even} \end{cases}\\ $$$

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

$$$ \text{Mod}(x) = \begin{cases} x - kMod, & \text{if } x \geq kMod \\ x + kMod, & \text{if } x < 0 \\ x, & \text{otherwise} \end{cases} $$$

The fourth function is the Dist Function

$$$ \text{Dist}(a, b) = \begin{cases} b - a, & \text{if } b > a \\ b + n - a, & \text{otherwise} \end{cases} $$$

The fifth function is the CrossProduct:

$$$ \text{CrossProduct}(a, b, c) = (a_x \times b_y + b_x \times c_y + c_x \times a_y) - (a_y \times b_x + b_y \times c_x + c_y \times a_x) $$$

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:

$$$ S_{ABC} = \frac{1}{2} \left| (x_A - x_B)(y_A + y_B) + (x_B - x_C)(y_B + y_C) + (x_C - x_A)(y_C + y_A) \right| \\ \text{Let A } =(x_A - x_B)(y_A + y_B) + (x_B - x_C)(y_B + y_C) + (x_C - x_A)(y_C + y_A) = (x_A \times y_B + x_B \times y_C + x_C \times y_A) - (y_A \times x_B + y_B \times x_C + y_C \times x_A)\\ \text{If } A > 0 \text{ Then the triangle is clockwise}\\ \text{If } A < 0 \text{ Then the triangle is counter clockwise}\\ \text{If } A = 0 \text{ Then 3 points are collinear} $$$

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:

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

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

$$$ \text{Let } f(i) \text{ be the total number of points that lie on one side of a line defined by point } i \text{ and point } P. $$$
$$$ \text{The total number of valid configurations is given by:} $$$
$$$ C_n^k - \sum_{i=0}^{n} C_{f(i)}^k \mod kMod $$$
$$$ \text{where:} $$$
$$$ \begin{align*} & C_n^k \text{ is the total number of ways to select } k \text{ points from } n. \\ & \sum_{i=0}^{n} C_{f(i)}^k \text{ is the sum of invalid configurations where all } k \text{ points lie on one side of the line.} \\ & \text{If } f(i) < k \text{, then } C_{f(i)}^k = 0 \text{ (since you can't choose } k \text{ points from fewer than } k \text{ points).} \\ & \mod kMod \text{ ensures the result fits within the modulus } kMod. \end{align*} $$$
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your clear and complete explanation, I really appreciate it!!!