Since the coordinates of the points are integers, the area of a triangle from any three points is an integer when doubled. The area of a convex hull can be calculated by fixing a point and decomposing the convex hull into triangles containing that point. Can we construct the “convex polygon that always contains a fixed point” by patching triangles one by one?

Let us consider if we can apply a known algorithm. One of the famous algorithms of constructing a convex hull is Monotone Chain. The outline is as follows:

• Sort the points in the increasing order of their \(x\) coordinates (and to break a tie, sort in the increasing order of \(y\) coordinates). The first point and the last point in the sorted list are always included in the convex hull.
• Inspect the points in the order, and construct the upper convex hull and the lower convex hull connecting those two points.

Similarly to the method above, we first sort the given points. Then, we try \(O(N)\) choices, fixing the left-bottom point (the point with the smallest \(y\) coordinates among the points with the smallest \(x\) coordinates).

Let \(P_i\) be the fixed point. Then, let us construct the upper convex hull and the lower convex hull by patching the triangles, one of whose points is \(P_i\). Consider the following DP (Dynamic Programming):

• \(\mathrm{upper}_{i, j, k}\): The number of sets of vertices \(S\) whose convex hull satisfies the following conditions:
  • When the points are inspected clockwise from \(P_s\), the last two points are \(P_i\) and \(P_j\), respectively.
  • Every point is above the line segment \(P_sP_j\).
  • The remainder of doubled area divided by \(2\) is \(k\).
• \(\mathrm{lower}_{i, j, k}\): The number of sets of vertices \(S\) whose convex hull satisfies the following conditions:
  • When the points are inspected counterclockwise from \(P_s\), the last two points are \(P_i\) and \(P_j\), respectively.
  • Every point is below the line segment \(P_sP_j\).
  • The remainder of doubled area divided by \(2\) is \(k\).

Then, the answer is the sum of \(\displaystyle \left( \sum_{i} \mathrm{upper}_{i, j, k} \right) \times \left( \sum_{i} \mathrm{lower}_{i, j, k} \right)\) for each \(j\) and \(k\).

Note that we need to precalculate for each triangle its area and the number of points in the interior of it. The total time complexity is \(O(N^4)\).

Sample Code (C++):

#include <iostream>
#include <algorithm>
#include <atcoder/modint>

struct Point {
    int x, y;
    explicit Point(const int x = 0, const int y = 0): x(x), y(y) {}
    bool operator < (const Point& other) const {
        return x < other.x or (x == other.x and y < other.y);
    }
    Point operator - (const Point& other) const {
        return Point(x - other.x, y - other.y);
    }
};

int cross(const Point& p, const Point& q) {
    return p.x * q.y - p.y * q.x;
}

using modint = atcoder::modint1000000007;

constexpr int MAX = 80;

int N;
Point P[MAX];

int inside[MAX][MAX][MAX], parity[MAX][MAX][MAX];
modint upper[MAX][MAX][2], lower[MAX][MAX][2];
modint pow2[MAX + 1];

// The doubled area of the tirangle
int area(const int i, const int j, const int k) {
    return std::abs(cross(P[j] - P[i], P[k] - P[i]));
}

int main() {
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].x >> P[i].y;
    }
    std::sort(P, P + N);
		// For each triangle, count the number of points in the interior of it
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                if (i == j or j == k or k == i) {
                    continue;
                }
                parity[i][j][k] = area(i, j, k) % 2;
                for (int l = 0; l < N; ++l) {
                    if (l != i and l != j and l != k and area(l, i, j) + area(l, j, k) + area(l, k, i) == area(i, j, k)) {
                        inside[i][j][k] += 1;
                    }
                }
            }
        }
    }
    // Precalculate the powers of 2
    pow2[0] = 1;
    for (int i = 0; i < N; ++i) {
        pow2[i + 1] = pow2[i] * 2;
    }
    modint ans = 0;
    for (int must = N - 1; must >= 0; --must) {
        // The convex polygon with P[must] as the leftmost point
        for (int i = must; i < N; ++i) {
            for (int j = must; j < N; ++j) {
                for (int k = 0; k < 2; ++k) {
                    upper[i][j][k] = lower[i][j][k] = 0;
                }
            }
        }
        for (int i = must + 1; i < N; ++i) {
            upper[must][i][0] = lower[must][i][0] = 1;
        }
        for (int i = must; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                for (int k = 0; k < 2; ++k) {
                    for (int l = j + 1; l < N; ++l) {
                        // Check the relative angle of the line segment P_iP_j and the line segment P_jP_l
                        if (cross(P[l] - P[j], P[j] - P[i]) > 0) {
                            // Patch a new triangle from three vertices  P_must, P_j, P_l
                            upper[j][l][k ^ parity[must][j][l]] += upper[i][j][k] * pow2[inside[must][j][l]];
                        }
                        else {
                            lower[j][l][k ^ parity[must][j][l]] += lower[i][j][k] * pow2[inside[must][j][l]];
                        }
                    }
                } 
            }
        }
        for (int j = must + 1; j < N; ++j) {
            for (int k = 0; k < 2; ++k) {
                modint up = 0, lo = 0;
                for (int i = must; i < j; ++i) {
                    up += upper[i][j][k];
                    lo += lower[i][j][k];
                }
                ans += up * lo;
            }
        }
    }
		// We have to exclude line segments that are counted as a convex polygon
    std::cout << (ans - N * (N - 1) / 2).val() << '\n';
    return 0;
}

Another solution

There is another algorithm of constructing a convex hull called Graham Scan, in which the points are sorted by their polar angles, and then inspected in order to construct the convex hull. One can apply this to a DP so that the convex hulls are counted without splitting into the upper and the lower parts.

Sample Code (Rust):

use proconio::{derive_readable, input};
use std::cmp::Ordering;
use std::ops::Sub;

#[derive_readable]
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
struct Point {
    x: i32,
    y: i32,
}

impl Sub for Point {
    type Output = Self;

    fn sub(self, other: Self) -> Self::Output {
        Self {
            x: self.x - other.x,
            y: self.y - other.y,
        }
    }
}

impl Point {
    fn cross(self, other: Self) -> i32 {
        self.x * other.y - self.y * other.x
    }
}

fn main() {
    input! {
        n: usize,
        mut pts: [Point; n],
    }
    pts.sort();
    let mut ans: u128 = 0;
    for leftmost in 0..n {
        let mut pts: Vec<_> = pts.iter().skip(leftmost).map(|&p| p - pts[leftmost]).collect();
        pts.sort_by(|&a, &b| {
            if a.cross(b) > 0 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        });
        let mut count = vec![vec![0; n]; n];
        for i in 0..pts.len() {
            for j in i + 1..pts.len() {
                for k in i + 1..j {
                    if (pts[i] - pts[k]).cross(pts[j] - pts[k]) > 0 {
                        count[i][j] += 1;
                    }
                }
            }
        }
        let mut dp = vec![vec![[0; 2]; n]; n];
        for j in 1..pts.len() {
            dp[0][j][0] += 1;
        }
        for i in 0..pts.len() {
            for j in i + 1..pts.len() {
                for k in 0..2 {
                    for l in j + 1..pts.len() {
                        if (pts[j] - pts[i]).cross(pts[l] - pts[j]) > 0 {
                            dp[j][l][k ^ (pts[j].cross(pts[l]).rem_euclid(2) as usize)] +=
                                dp[i][j][k] * (1 << count[j][l]);
                        }
                    }
                }
            }
        }
        for i in 1..pts.len() {
            for j in i + 1..pts.len() {
                ans += dp[i][j][0];
            }
        }
    }
    println!("{}", ans % 1000000007);
}

Similar problem

Japanese Olympiad in Informatics (JOI) Spring Camp 2008 - 「最古の遺跡 2」 (The problem statement is in Japanese.)