PLYARSM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Daanish Mahajan
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Medium

PREREQUISITES:

Convex Hull, Two Pointers

PROBLEM:

You are given a convex polygon P with N vertices. The vertices (in clockwise order) are v_1, v_2, \dots v_N. The coordinates of v_i are (x_i, y_i). All vertices have integer coordinates.

A diagonal of P is a line segment l joining two distinct vertices v_i and v_j of P, such that l is not already an edge of P. Every diagonal of P splits it into two smaller convex polygons, both having positive areas.

The evenness of a diagonal of P is the minimum of the areas of the two parts obtained when the polygon P is cut along this diagonal.

Let S be the sum of the evenness of all diagonals of P.

Find the value of 2S \pmod{998244353}.

QUICK EXPLANATION:

Subtask 1

Let points P_i and P_j denote the diagonal of the polygon. Note that since it is a diagonal, P_i and P_j should not be adjacent points on the polygon.

We separate all the points lying between P_i and P_j (both included) and calculate the area of the polygon made using those points. This is the area of one part. We can subtract this from the total area of the polygon and take the minimum value to calculate the evenness of diagonal (P_i,P_j).

We iterate over all possible combinations of (P_i,P_j) in O(N^2). For each pair, we calculate the area of the polygon made by points P_k (i \leq k \leq j) in O(N) time. Thus, the overall complexity of this solution is O(N^3) which is sufficient to pass this subtask.

Subtask 2

While calculating the area of the polygon made using diagonal (P_i,P_j), we iterate over all the points to calculate the area. This area can be calculated more efficiently.

Suppose we have the area of the polygon formed using diagonal (P_i, P_{j-1}). For diagonal (P_i,P_j), we are just adding another triangle formed by points (P_i, P_{j-1}, P_j). The area of this triangle can be calculated in O(1).

Thus, each time we can calculate the area of a polygon made using diagonal (P_i,P_j) by using the result of diagonal (P_i,P_{j-1}). The complexity of calculating the area now becomes O(1).

We iterate through all possible diagonals in O(N^2) can calculate the area for each in O(1). The overall complexity of this approach is O(N^2) which is sufficient to pass this subtask.

Subtask 3

Let A denote the total area of the polygon.

For each point P_i, we find the point P_j upto which the area of the polygon formed by points P_k (i \leq k \leq j) is X and X \leq A.
To calculate this, we can use the two-pointer technique.

Detailed explanation for two-pointer technique

Assume that the total area of the polygon is A.
Consider a diagonal (P_i, P_k). We consider the polygon made by points in the clockwise direction starting from P_i, i.e, (P_i, P_{i+1}, P_{i+2}, ...,P_k, P_i). Let B_{(i, k)} denote the area of this polygon.

  • Moving the right pointer would be extending point P_k to P_{k+1} (in clockwise direction). A new polygon is formed by points (P_i, P_{i+1}, ..., P_{k},P_{k+1}, P_i). The area of this polygon can be calculated as B_{(i, k+1)} = B_{(i, k)} + area of triangle (P_i, P_k, P_{k+1}). Note that B_{(i, k+1)} can be calculated in O(1) since we already have the value of B_{(i, k)}.
  • We extend P_k till point P_j such that the area of polygon formed by diagonal (P_i, P_j) is B_{(i, j)} \leq \frac{A}{2} < B_{(i, j+1)}.
  • Since B_{(i, j)} \leq \frac{A}{2}, we can also say that B_{(i, k)} \leq \frac{A}{2} where (i+1 < k \leq j). In other words, all the polygons of the form:
    – (P_i, P_{i+1}, P_{i+2}, P_i)
    – (P_i, P_{i+1}, P_{i+2},P_{i+3}, P_i)
    – …
    – (P_i, P_{i+1}, P_{i+2}, ...,P_j, P_i)
    have areas less \frac{A}{2}. This ensures that these polygons have areas less than their other part.
  • Once we have P_j for a given P_i, we can add the areas of all polygons formed by diagonals (P_i, P_k) where (i+1 < k \leq j) to the final answer. Now, we have the contribution of all diagonals starting from P_i and moving in clockwise direction. We do the same process for diagonals starting from P_i and moving in anticlockwise direction.
  • Since we already have the contribution of P_i, we can increment the left pointer from P_i to P_{i+1}. The right pointer is currently at P_j. Based on the value B_{(i+1, j)}, we decide if we need to increment the left pointer or the right pointer.
    – If B_{(i+1, j)} \leq \frac{A}{2}, we increment the right pointer from P_j to P_{j+1}.
    – Else, we increment the left pointer from P_{i+1} to P_{i+2}.

Once we have P_j for a given P_i, all the polygons:

  • P_i, P_{i+1}, P_{i+2}, P_i
  • P_i, P_{i+1}, P_{i+2}, P_{i+3}, P_i
  • …
  • P_i, P_{i+1}, P_{i+2}, P_{i+3}, ..., P_j, P_i

are smaller (have lesser area) compared to the other part.

The area of all these polygons can be calculated using some precomputation in the shoelace formula used for calculating the area.

Note that till now, we have not considered diagonals of the form (P_i, P_k) (k >j) for a given P_i. For the contribution of those diagonals, we can consider points in anticlockwise direction starting from P_i.

The complexity of this solution would be O(N) since we are using two-pointers technique. See setter’s solution for implementation details.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long

const int MAX = (int)1e6 + 1;

int x[MAX + 1], y[MAX + 1], n;
LL ai[MAX + 1], bi[MAX + 1], ci[MAX + 1], A[MAX + 1], B[MAX + 1], C[MAX + 1], SA[MAX + 1], SB[MAX + 1], SC[MAX + 1];

// Find area of triangle v_a, v_b, v_c
LL area(int a, int b, int c) {
    assert(a >= 1 && a <= n); assert(b >= 1 && b <= n); assert(c >= 1 && c <= n);
    LL ret = x[a] * 1LL * (y[b] - y[c]) + x[b] * 1LL * (y[c] - y[a]) + x[c] * 1LL * (y[a] - y[b]);
    if (ret < 0) ret = -ret;
    return ret;
}
// sum of delta_ij over j = i to r
LL prefsumdelta_mod(int i, int r) {
    assert(r >= i);
    if (r < i + 2) return 0;
    LL ret = ((x[i] * 1LL * (SA[r-1] - SA[i]) + y[i] * 1LL * (SB[r-1] - SB[i]) + SC[r-1] - SC[i]) % MOD) - ((r - i - 1) * 1LL * ((x[i] * 1LL * A[i] + y[i] * 1LL * B[i] + C[i]) % MOD)) % MOD;
    ret %= MOD;
    if (ret < 0) ret += MOD;
    return ret;
}

// O(n^3) solution
LL solve_ncube() {
    LL delta = 0, ans = 0;
    for (int i=1;i<n;++i) {
        delta += area(1, i, i+1);
    }
    for (int i=1;i<=n;++i) {
        for (int j=i+2;j<=n;++j) {
            LL now = 0;
            for (int k=i+1;k<j;++k) {
                now += area(i, k, k + 1);
            }
            ans += min(now, delta - now);
            ans %= MOD;
        }
    }
    return ans;
}
// O(n^2) solution
LL solve_nsquare() {
    LL delta = 0, ans = 0;
    for (int i=1;i<n;++i) delta += area(1, i, i+1);
    for (int i=1;i<=n;++i) {
        LL now = 0;
        for (int j=i+1;j<=n;++j) {
            now += area(i, j-1, j);
            ans += min(now, delta - now);
            ans %= MOD;
        }
    }
    return ans;
}

// read input for one testcase
void read() {
    cin >> n;
    for (int i=1;i<=n;++i) {
        cin >> x[i] >> y[i];
    }
}

// O(n) solution
LL solve_linear() {
    LL ans = 0, delta = 0;
    A[0] = B[0] = C[0] = 0;
    SA[0] = SB[0] = SC[0] = 0;
    for (int i=1;i<=n;++i) {
        ai[i] = A[i] = SA[i] = 0;
        bi[i] = B[i] = SB[i] = 0;
        ci[i] = C[i] = SC[i] = 0;
    }
    for (int j=1;j<=n;++j) {
        int k = (j == n ? 1 : j + 1);
        LL a, b, c;
        a = y[j] - y[k]; b = x[k] - x[j]; c = x[j] * 1LL * y[k] - x[k] * 1LL * y[j];
        for (int p = 1; p <= 3; ++p) {
            if (a * 1LL * x[p] + b * 1LL * y[p] + c < 0) {
                a *= -1; b *= -1; c *= -1;
            }
        }
        for (int p = 1; p <= 3; ++p) {
            assert(a * 1LL * x[p] + b * 1LL * y[p] + c >= 0);
        }
        ai[j] = a; bi[j] = b; ci[j] = c;
        A[j] = A[j-1] + a; B[j] = B[j-1] + b; C[j] = C[j-1] + c;
        A[j] %= MOD; B[j] %= MOD; C[j] %= MOD;
        SA[j] = SA[j-1] + A[j]; SB[j] = SB[j-1] + B[j]; SC[j] = SC[j-1] + C[j];
        SA[j] %= MOD; SB[j] %= MOD; SC[j] %= MOD;
        if (j < n) delta += area(1, j, j + 1);
    }
    int k = 1;
    LL delta_ik = 0;
    for (int i=1;i<=n-2;++i) {
        while (k <= n && delta_ik * 2 < delta) {
            k++;
            if (k > n) break;
            delta_ik += area(i, k-1, k);
        }
        ans += ((n - k + 1) * 1LL * (delta % MOD) - prefsumdelta_mod(i, n) % MOD + 2LL * prefsumdelta_mod(i, k-1) % MOD) % MOD;
        if (ans >= MOD) ans -= MOD;
        if (ans < 0) ans += MOD;
        if (k <= n) delta_ik -= area(i, i+1, k);
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        read();
        LL A = solve_linear();
        cout << A << '\n';
    } 
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define mod 998244353
using namespace std;

vector<pair<ll, ll>> pt, ppt;
int n;

ll area(int a, int b, int c) {
    return abs(pt[a].first*(pt[b].second - pt[c].second) + pt[b].first*(pt[c].second - pt[a].second) + pt[c].first*(pt[a].second - pt[b].second));
}

ll prefarea(int i, int l, int r) {
    ll val;
    if(l > r) {
        val = (((pt[i].first*pt[l].second - pt[l].first*pt[i].second + mod)%mod)*(n + r - l))%mod;
        val %= mod;
        val += (((pt[i].second - pt[l].second)*(ppt[n - 1].first + ppt[r].first - ppt[l].first))%mod+((pt[l].first - pt[i].first)*(ppt[n - 1].second + ppt[r].second - ppt[l].second))%mod)%mod;
        val %= mod;
    } else {
        val = (((pt[i].first*pt[l].second - pt[l].first*pt[i].second + mod)%mod)*(r - l))%mod;
        val %= mod;
        val += (((pt[i].second - pt[l].second)*(ppt[r].first - ppt[l].first))%mod+((pt[l].first - pt[i].first)*(ppt[r].second - ppt[l].second))%mod)%mod;
        val %= mod;
    }
    return val;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> n;
	    pt.clear();
	    pt.resize(n);
	    for(int i = 0; i < n; i++) {
	        cin >> pt[i].first >> pt[i].second;
	    }
	    ll ar = 0;
	    for(int i = 1; i < n - 1; i++) {
	        ar += area(0, i, i + 1);
	    }
	    ppt.clear();
	    ppt.resize(n);
	    ppt[0] = pt[0];
	    for(int i = 1; i < n; i++) ppt[i].first = (ppt[i - 1].first + pt[i].first)%mod, ppt[i].second = (ppt[i - 1].second + pt[i].second)%mod;
	    ll ans = 0, cur = 0, now = 0;
	    ll st = 0, en = 1;
	    int done[n];
	    memset(done, 0, sizeof(done));
	    for(int i = 0; i < n; i++) {
	        ans += cur;
	        ans %= mod;
	        now += area(i, st, en);
	        while(now <= ar - now) {
	            if(now == ar - now && done[i]) break;
	            if(now == ar - now) done[en] = 1;
	            ans += now, ans %= mod;
	            cur += now, cur %= mod;
	            st++;
	            st %= n;
	            en++;
	            en %= n;
	            now += area(i, st, en);
	        }
	        int nxt = (i + 1)%n;
	        now -= (area(i, st, en) + area(i, nxt, st));
	        cur += prefarea(i, nxt, st);
	        cur %= mod;
	    }
	    while(ans < 0) ans += mod;
	    cout << ans << "\n";
	}
	return 0;
}
1 Like

Is there a Video Editorial for this problem? I am finding it difficult to understand how to move the two-pointers. Or can anyone explain the movement of pointers with the help of an example?

1 Like

I have added a detailed explanation for two-pointer technique. Hope it helps! :slight_smile:

1 Like

That looks great and informative. Thanks a lot.

1 Like