Matcom Online Grader

ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.

ACM 2014 - Round #1

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Rating changes
Virtual participation

Register

Are you sure you want to participate in this contest ?

D - Polígono

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#

Time & Memory limits: (details)

Dado N puntos diferentes en el plano, escriba un programa que determine la menor área de un polígono convexo con K vértices tomados de los N puntos iniciales. Se garantiza que ningún trío yace sobre una misma recta. Suponga que N = 4, K = 3 y la lista de puntos es (0, 0), (1, 1), (0, 10) y (10, 0). De todos los triángulos que se pueden formar hay dos con área mínima igual a 5.0, el primero {(0, 0), (1, 1), (0, 10)} y el segundo {(0, 0), (1, 1), (10, 0)}.

Input

Línea 1 : Dos enteros N y K separados por espacio (1 <= N <= 50, 1 <= K <= 10).
Línea 2...N+1 : Dos enteros por línea X e Y separados por espacio representando los puntos (0 <= X, Y <= 10000).

Output

Línea 1 : Un solo número igual a la parte entera de la menor área. Si no existe un polígono convexo de K puntos, entonces su programa debe imprimir 0.

Sample test(s)

Input

4 3 0 0 1 1 0 10 10 0

Output