URI Online Judge | 2907

Escape, Polygon!

By Guilherme A. Pinto BR 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 defines 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 define a triangle since two of them are parallel, and so the polygon will escape. In (c), the polygon lies outside the triangle defined 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.


The first 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 define a simple convex polygon. No three vertices are collinear.


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


0 0

10 0

10 10

0 5



0 32

-12 15

-10 -10

0 -12

10 -12

22 0

25 10

18 20



10 -10

0 10

-10 -10