Official Analysis (C++)

Explanation

Let's consider the right triangles we can create if we consider every coordinate as the point of the right angle. If we have a point $\left(x,y\right)$ as the right angle point, then the other two vertices must be $\left(a,y\right)$ and $\left(x,b\right)$ (one with the same $x$-coordinate and another with the same $y$-coordinate).

Pairing this $\left(a,y\right)$ and $\left(x,b\right)$ means two times the area of this triangle is $\left|x-a\right|\cdot\left|y-b\right|$. Thus, the total contribution for some $\left(x,y\right)$ is $(\sum_{a∈A}\left|x-a\right|)\cdot(\sum_{b∈B}\left|y-b\right|)$.

To do this for each coordinate, we can store the $y$-values for each $x$ and the $x$-values for each $y$. Then, we sort the $y$-values for each $x$ and the $x$-values for each $y$, and use prefix sums to compute the distance from all $x$-values and distance from all $y$-values in the lists. For each point, multiply the total horizontal distance and total vertical distance to add that to the total answer.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>

using namespace std;

void setIO(string prob = "") {
	if (!prob.empty()) {
		freopen((prob + ".in").c_str(), "r", stdin);
		freopen((prob + ".out").c_str(), "w", stdout);
	}
}

Copy
import java.io.*;
import java.util.*;

public class Triangles {
	static class Fence {
		int x;
		int y;
		// terminology: anchor point = vertex of the right angle in a right
		// triangle sum of heights of all triangles that use this fence as an
		// anchor point

Copy
import itertools
import bisect

MOD = 10**9 + 7

with open("triangles.in", "r") as read:
	n = int(read.readline())
	coordinates = []
	x_values = dict()
	y_values = dict()