Triangles
Solución en video
Por I-Chen Chou
Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++ y Java.
Video de YouTube (eHr6xw163CU)
Solución
Explicación
Consideremos los triángulos rectángulos que podemos crear si tomamos cada coordenada como el punto del ángulo recto. Si tenemos un punto como vértice del ángulo recto, entonces los otros dos vértices deben ser y (uno con la misma coordenada y otro con la misma coordenada ).
Emparejar este y significa que el doble del área de este triángulo es . Así, la contribución total de algún es .
Para hacer esto para cada coordenada, podemos guardar los valores de para cada y los valores de para cada . Luego ordenamos los valores de para cada y los de para cada , y usamos sumas de prefijos para calcular la distancia a todos los valores de y a todos los valores de de las listas. Para cada punto, multiplicamos la distancia horizontal total y la distancia vertical total y lo sumamos a la respuesta total.
Implementación
Complejidad temporal:
#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);
}
}
const int MAX_N = 1e5;
const int MOD = 1e9 + 7;
const int MAX_C = 1e4;
struct Fence {
int x;
int y;
// terminología: punto ancla = vértice del ángulo recto en un triángulo rectángulo
// suma de las alturas de todos los triángulos que usan esta cerca como punto ancla
long long heightsum;
// suma de las bases de todos los triángulos que usan esta cerca como punto ancla
long long basesum;
};
Fence fences[MAX_N];
// todas las coordenadas x posibles de las cercas (+1 para tener en cuenta el 0)
vector<pair<int, int>> xcoords[2 * MAX_C + 1];
// todas las coordenadas y posibles de las cercas
vector<pair<int, int>> ycoords[2 * MAX_C + 1];
int main() {
setIO("triangles");
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> fences[i].x >> fences[i].y;
// sumamos MAX_C para que todas nuestras coordenadas sean positivas
// y no tengamos índices negativos
xcoords[fences[i].x + MAX_C].push_back({fences[i].y, i});
ycoords[fences[i].y + MAX_C].push_back({fences[i].x, i});
}
for (int i = 0; i <= 2 * MAX_C; i++) {
if (xcoords[i].size() > 0) {
// curr es el valor del s_i actual
long long curr = 0;
// ordenar todas las posiciones y de todos los puntos con la misma x
sort(xcoords[i].begin(), xcoords[i].end());
/*
* luego calculamos el valor s_1 de este conjunto:
* la suma de las alturas de todos los triángulos que
* tienen su punto ancla en (i, xcoords[i][0].first)
*/
for (int j = 1; j < xcoords[i].size(); j++) {
curr += xcoords[i][j].first - xcoords[i][0].first;
}
fences[xcoords[i][0].second].heightsum = curr;
// luego calculamos el resto de los s_i de este conjunto
for (int j = 1; j < xcoords[i].size(); j++) {
curr += (2 * j - xcoords[i].size()) *
(xcoords[i][j].first - xcoords[i][j - 1].first);
fences[xcoords[i][j].second].heightsum = curr;
}
}
}
// hacemos las sumas de las bases exactamente de la misma forma
for (int i = 0; i <= MAX_C * 2; i++) {
if (ycoords[i].size() > 0) {
long long curr = 0;
sort(ycoords[i].begin(), ycoords[i].end());
for (int j = 1; j < ycoords[i].size(); j++) {
curr += ycoords[i][j].first - ycoords[i][0].first;
}
fences[ycoords[i][0].second].basesum = curr;
for (int j = 1; j < ycoords[i].size(); j++) {
curr += (2 * j - ycoords[i].size()) *
(ycoords[i][j].first - ycoords[i][j - 1].first);
fences[ycoords[i][j].second].basesum = curr;
}
}
}
long long total_area = 0;
for (int i = 0; i < n; i++) {
total_area += fences[i].heightsum * fences[i].basesum % MOD;
total_area %= MOD;
}
cout << total_area << '\n';
}import java.io.*;
import java.util.*;
public class Triangles {
static class Fence {
int x;
int y;
// terminología: punto ancla = vértice del ángulo recto en un
// triángulo rectángulo; suma de las alturas de todos los triángulos
// que usan esta cerca como punto ancla
long heightsum;
// suma de las bases de todos los triángulos que usan esta cerca como
// punto ancla
long basesum;
}
static class Pair implements Comparable<Pair> {
int first, second;
public Pair(int x, int y) {
first = x;
second = y;
}
public int compareTo(Pair x) {
if (this.first == x.first) return this.second - x.second;
return this.first - x.first;
}
}
static final int MOD = (int)1e9 + 7;
static final int MAX_C = (int)1e4;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader("triangles.in"));
PrintWriter pw = new PrintWriter("triangles.out");
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
Fence[] fences = new Fence[n];
// todas las coordenadas x posibles de las cercas (+1 para tener en cuenta el 0)
ArrayList<Pair>[] xcoords = new ArrayList[2 * MAX_C + 1];
// todas las coordenadas y posibles de las cercas
ArrayList<Pair>[] ycoords = new ArrayList[2 * MAX_C + 1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(in.readLine());
fences[i] = new Fence();
fences[i].x = Integer.parseInt(st.nextToken());
fences[i].y = Integer.parseInt(st.nextToken());
// sumamos MAX_C para que todas nuestras coordenadas sean positivas
// y no tengamos índices negativos
if (xcoords[fences[i].x + MAX_C] == null)
xcoords[fences[i].x + MAX_C] = new ArrayList<>();
if (ycoords[fences[i].y + MAX_C] == null)
ycoords[fences[i].y + MAX_C] = new ArrayList<>();
xcoords[fences[i].x + MAX_C].add(new Pair(fences[i].y, i));
ycoords[fences[i].y + MAX_C].add(new Pair(fences[i].x, i));
}
for (int i = 0; i <= 2 * MAX_C; i++) {
if (xcoords[i] != null) {
// cur es el valor del s_i actual
long cur = 0;
// ordenar todas las posiciones y de todos los puntos con la misma x
Collections.sort(xcoords[i]);
/*
* luego calculamos el valor s_1 de este conjunto:
* la suma de las alturas de todos los triángulos que
* tienen su punto ancla en (i, xcoords[i][0].first)
*/
for (int j = 1; j < xcoords[i].size(); j++) {
cur += xcoords[i].get(j).first - xcoords[i].get(0).first;
}
fences[xcoords[i].get(0).second].heightsum = cur;
// luego calculamos el resto de los s_i de este conjunto
for (int j = 1; j < xcoords[i].size(); j++) {
cur += (2 * j - xcoords[i].size()) *
(xcoords[i].get(j).first - xcoords[i].get(j - 1).first);
fences[xcoords[i].get(j).second].heightsum = cur;
}
}
}
// hacemos las sumas de las bases exactamente de la misma forma
for (int i = 0; i <= 2 * MAX_C; i++) {
if (ycoords[i] != null) {
long cur = 0;
Collections.sort(ycoords[i]);
for (int j = 1; j < ycoords[i].size(); j++) {
cur += ycoords[i].get(j).first - ycoords[i].get(0).first;
}
fences[ycoords[i].get(0).second].basesum = cur;
for (int j = 1; j < ycoords[i].size(); j++) {
cur += (2 * j - ycoords[i].size()) *
(ycoords[i].get(j).first - ycoords[i].get(j - 1).first);
fences[ycoords[i].get(j).second].basesum = cur;
}
}
}
// por último calculamos el área total
int totalArea = 0;
for (int i = 0; i < n; i++) {
totalArea += fences[i].heightsum * fences[i].basesum % MOD;
totalArea %= MOD;
}
pw.println(totalArea);
pw.close();
}
}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()
for i in range(n):
x, y = map(int, read.readline().split())
coordinates.append((x, y))
# guardar valores de y para cada x y valores de x para cada y en tablas hash
if x in x_values:
x_values[x].append(y)
else:
x_values[x] = [y]
if y in y_values:
y_values[y].append(x)
else:
y_values[y] = [x]
# ordenar los valores de y para cada x y los de x para cada y
for x in x_values:
x_values[x].sort()
for y in y_values:
y_values[y].sort()
# crear listas de sumas de prefijos para los valores de y de cada x y los de x de cada y con itertools
x_prefix = x_values.copy()
y_prefix = y_values.copy()
for x in x_prefix:
x_prefix[x] = [0] + list(itertools.accumulate(x_prefix[x]))
for y in y_prefix:
y_prefix[y] = [0] + list(itertools.accumulate(y_prefix[y]))
ans = 0
# recorrer todas las coordenadas (x, y) como punto del ángulo recto
for x, y in coordinates:
# búsqueda binaria de índices en los mapas de coordenadas x e y con bisect
x_index = bisect.bisect_left(x_values[x], y)
y_index = bisect.bisect_left(y_values[y], x)
# hallar la suma de distancias de y a todos los valores de y usando sumas de prefijos
x_sum = (
y * x_index
- x_prefix[x][x_index]
+ x_prefix[x][len(x_values[x])]
- x_prefix[x][x_index + 1]
- (y * (len(x_values[x]) - x_index - 1))
)
# hallar la suma de distancias de x a todos los valores de x usando sumas de prefijos
y_sum = (
x * y_index
- y_prefix[y][y_index]
+ y_prefix[y][len(y_values[y])]
- y_prefix[y][y_index + 1]
- (x * (len(y_values[y]) - y_index - 1))
)
# sumar las áreas de los triángulos (producto de x_sum e y_sum) a la respuesta
ans += x_sum * y_sum
print(ans % MOD, file=open("triangles.out", "w"))