Carnival

Written by Raouf Ould Ali.

Problem Statement

• English
• French
• Arabic

We are given lattice points (), with the guarantee that no three points are collinear. For every triple of points , these form a triangle. The score of this triangle is the number of points lying strictly inside it (excluding its vertices). The task is to output, for each possible score , how many triangles contain exactly points.

---

Key Observations

• Naïve approach For each triangle , check every other point to see if it lies inside.

  • This is : there are triangles, and each check costs .
  • With , this is too slow.

• Sorting helps The first step in the solution is to sort the points by their -coordinates.

  • After sorting, any triangle with will have its vertices ordered with respect to the component.
  • This prevents double-counting and ensures that the points_below[i][j] values behave consistently when we combine them.

---

Precomputation: Points under a segment

For two points and (), consider the directed segment . We count how many points with indices strictly between and lie strictly to the right of this line.

Formally:

This preprocessing costs .

---

Using the precomputation for triangles

Now, for each triple with , we want to compute the number of points inside the triangle .

• If the orientation is counter-clockwise:

• If the orientation is clockwise:

We then increment the counter:

---

Complexity Analysis

• Sorting:
• Precomputation: for filling points_below
• Triangle enumeration:
• Total: , which is efficient for .

Memory: for points_below.

Implementation

#include <bits/stdc++.h>
#define int long long
using namespace std;

int cross_product(int x1, int y1, int x2, int y2)
{
    return x1 * y2 - x2 * y1;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> point(n);
    for (int i = 0; i < n; i++)
        cin >> point[i].first >> point[i].second;

    sort(point.begin(), point.end());

    vector<vector<int>> points_below(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            for (int k = i + 1; k < j; k++)
            {
                if (cross_product(point[j].first - point[i].first,
                                  point[j].second - point[i].second,
                                  point[k].first - point[i].first,
                                  point[k].second - point[i].second) < 0)
                {
                    points_below[i][j] += 1;
                }
            }
        }

    vector<int> O(n - 2, 0);

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
            {
                if (cross_product(point[j].first - point[i].first,
                                  point[j].second - point[i].second,
                                  point[k].first - point[i].first,
                                  point[k].second - point[i].second) > 0)
                {
                    O[points_below[i][k] - points_below[i][j] - points_below[j][k] - 1] += 1;
                }
                else
                {
                    O[points_below[i][j] + points_below[j][k] - points_below[i][k]] += 1;
                }
            }

    for (int i = 0; i < n - 2; i++)
        cout << O[i] << ' ';
}