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