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<N105) Siguen N coordenadas enteras cuyo valor absoluto no es más que 109. Para el 40% de los casos de prueba N400.

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

Copy
5
0 0
2 0
0 2
1 1
2 2

Ejemplo de Salida

Copy
4
0 0
0 2
2 0
2 2
4.0
Descripcion

Comments

There are no comments at the moment.