2907 - Escape, Polygon!

  • ID: 2907
  • IdBecrowd: 2907
  • Tags: geometria
  • Nível: 10
  • Tempo Limite: 1.000s
  • Memória: 256MB
  • Categoria: Geometria Computacional
  • Autor: Vinicius Reis (Brasil)

Descrição

A convex polygon is given. Three lines are chosen, each coinciding with one of the polygon’s sides. These three lines define a triangle. The polygon is “locked” if it lies completely inside the triangle formed by these three lines. If the lines do not form a triangle (e.g., if two are parallel), or if the polygon is not entirely contained within the triangle, it escapes. The goal is to count how many unique combinations of three distinct sides will result in the polygon being locked.

Entrada

The first line of input contains an integer N (where 3 <= N <= 10^5), representing the number of vertices of the polygon. Each of the subsequent N lines contains two integers, X and Y (where -10^8 <= X, Y <= 10^8), indicating the coordinates of a vertex in the XY plane. The vertices are given in counter-clockwise order.

Saída

The output should be a single integer, representing the number of distinct triples of lines (sides) that can lock the given polygon.

Exemplos

Exemplo de Entrada

4
0 0
10 0
10 10
0 10

Exemplo de Saída

0

Exemplo de Entrada

3
0 0
10 0
5 10

Exemplo de Saída

1
Back to top