Skip to Content

Triangles

Análisis oficial (C++) 

Explicación

Probamos por fuerza bruta todos los triángulos rectángulos posibles recorriendo todas las ternas de puntos y comprobando si forman un triángulo rectángulo. Si es así, calculamos el área y hallamos el máximo entre todos los triángulos rectángulos.

Implementación

Complejidad temporal: O(N3)\mathcal{O}(N^3)

#include <bits/stdc++.h> using namespace std; int main() { freopen("triangles.in", "r", stdin); int n; cin >> n; vector<int> x(n); // coordenadas x de todos los postes de la cerca vector<int> y(n); // coordenadas y de todos los postes de la cerca for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } int max_area = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // Comprobamos si ambos puntos son paralelos a los ejes x e y if (y[i] == y[j] && x[i] == x[k]) { int area = abs((x[j] - x[i]) * (y[k] - y[i])); max_area = max(max_area, area); } } } } freopen("triangles.out", "w", stdout); cout << max_area << endl; }
import java.io.*; import java.util.*; public class Triangles { public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new FileReader("triangles.in")); int n = Integer.parseInt(read.readLine()); int[] x = new int[n]; // coordenadas x de todos los postes de la cerca int[] y = new int[n]; // coordenadas y de todos los postes de la cerca for (int i = 0; i < n; i++) { StringTokenizer fencePost = new StringTokenizer(read.readLine()); x[i] = Integer.parseInt(fencePost.nextToken()); y[i] = Integer.parseInt(fencePost.nextToken()); } read.close(); int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // Comprobamos si ambos puntos son paralelos a los ejes x e // y if (y[i] == y[j] && x[i] == x[k]) { int area = Math.abs((x[j] - x[i]) * (y[k] - y[i])); maxArea = Math.max(maxArea, area); } } } } PrintWriter written = new PrintWriter("triangles.out"); written.println(maxArea); written.close(); } }
with open("triangles.in") as read: n = int(read.readline()) x = [] # coordenadas x de todos los postes de la cerca y = [] # coordenadas y de todos los postes de la cerca for _ in range(n): x_i, y_i = [int(i) for i in read.readline().split()] x.append(x_i) y.append(y_i) max_area = 0 for i in range(n): for j in range(n): for k in range(n): # Comprobamos si ambos puntos son paralelos a los ejes x e y if y[i] == y[j] and x[i] == x[k]: area = abs((x[j] - x[i]) * (y[k] - y[i])) max_area = max(max_area, area) print(max_area, file=open("triangles.out", "w"))