Triangles.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

El Granjero Juan quiere crear un pastizal triangular para sus vacas.

Hay N postes de cerca en puntos distintos (X_1,Y_1) \ldots (X_N,Y_N) en el mapa 2D de la granja. El puede elegir tres de ellos como los vértices del pastizal triangular en tanto uno de los lados del triángulo sea paralelo al eje x y otro sea paralelo al eje y.

¿Cuál es el área máxima de un pastizal que el Granjero Juan puede formar? Se garantiza que al menos existe un pastizal triangular válido.

Entrada

La primera línea de la entrada contiene el entero N (3 \leq N \leq 100). Cada una de las siguientes N líneas contiene dos enteros X_i y Y_i, cada uno en el rango -10^4 \ldots 10^4 inclusive, describiendo las posiciones de un poste de cerca.

Salida

Como el área misma no es necesariamente un entero, dé como salida el área máxima de un triángulo válido formado por los postes de cerca por dos.

Ejemplo de Entrada

4
0 0
0 1
1 0
1 2

Ejemplo de Salida

2

Los postes en (0,0), (1,0) y (1,2) forman un triángulo de área 1. Por lo tanto, la respuesta es 2 \cdot 1 = 2. Unicamente hay otro triángulo, con área 0.5.

USACO 2020 February Contest, Bronze. Problem 1. Triangles.


Comments

There are no comments at the moment.