Skip to Content

Triangles

Análisis oficial (C++) 

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 (x,y)\left(x,y\right) como vértice del ángulo recto, entonces los otros dos vértices deben ser (a,y)\left(a,y\right) y (x,b)\left(x,b\right) (uno con la misma coordenada xx y otro con la misma coordenada yy).

Emparejar este (a,y)\left(a,y\right) y (x,b)\left(x,b\right) significa que el doble del área de este triángulo es xayb\left|x-a\right|\cdot\left|y-b\right|. Así, la contribución total de algún (x,y)\left(x,y\right) es (aAxa)(bByb)(\sum_{a∈A}\left|x-a\right|)\cdot(\sum_{b∈B}\left|y-b\right|).

Para hacer esto para cada coordenada, podemos guardar los valores de yy para cada xx y los valores de xx para cada yy. Luego ordenamos los valores de yy para cada xx y los de xx para cada yy, y usamos sumas de prefijos para calcular la distancia a todos los valores de xx y a todos los valores de yy 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: O(NlogN)\mathcal{O}(N\log N)

#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"))