Country Hull


Submit solution

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

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Este problema no tiene ninguna historia, ya es suficientemente difícil y se divertirán programándolo, no necesitan más diversión que esa. Dados N puntos en el plano diga cuáles pertenecen a su Convex Hull y diga el área de este. El convex hull es el polígono convexo con menor área que contiene a todos los puntos (vea la imagen del ejemplo).

Entrada

La primera línea contiene un entero N (0 < N \leq 10^5) Siguen N coordenadas enteras cuyo valor absoluto no es más que 10^9. Para el 40% de los casos de prueba N \leq 400.

Salida

Imprima un entero X, la cantidad de puntos que pertenecen al convex hull. Luego imprima X pares ordenados lexicográficamente, los cuales son los puntos que pertenecen al convex hull, además debe cumplir la propiedad de que no existan tres puntos de estos que pertenezcan a la misma recta, en ese caso se imprimen los dos más alejados entre sí. Por último imprima el área del convex hull, usando de precisión un solo lugar después de la coma.

Ejemplo de Entrada

5
0 0
2 0
0 2
1 1
2 2

Ejemplo de Salida

4
0 0
0 2
2 0
2 2
4.0
Descripcion

Comments

There are no comments at the moment.