﻿ URI 2907 - Escape, Polygon!
URI Online Judge | 2907

# Escape, Polygon!

By Guilherme A. Pinto Brazil

Timelimit: 1

A suspicious-looking convex polygon wants to escape its current position by translating itself along some straight-line direction. Three very diligent straight lines want to lock it up by placing themselves along three distinct sides of the polygon. Then, if the triple of lines deﬁnes a triangle and the polygon lies inside this triangle, it will be locked up. Otherwise, it will escape.

Figure (a) above illustrates a triple that will lock the polygon up. For (b), the lines do not deﬁne a triangle since two of them are parallel, and so the polygon will escape. In (c), the polygon lies outside the triangle deﬁned by the triple and it will easily escape.

Given a polygon, you must compute the number of distinct triples of lines that can lock the polygon up.

## Input

The ﬁrst line contains an integer N (3 ≤ N ≤ 105) representing the number of vertices of the polygon. Each of the next N lines describes a vertex with two integers X and Y (−108 X,Y ≤ 108) indicating the coordinates of the vertex in the XY plane. The vertices are given in counter-clockwise order and they deﬁne a simple convex polygon. No three vertices are collinear.

## Output

Output a single line with an integer indicating the number of distinct triples of lines that can lock the given polygon up.

 Input Samples Output Samples 4 0 0 10 0 10 10 0 5 1
 8 0 32 -12 15 -10 -10 0 -12 10 -12 22 0 25 10 18 20 18
 3 10 -10 0 10 -10 -10 1