Another Contest 9 Problem 5 - Satellite

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 256M

Problem types

From atop a satellite, Nick has drawn N lines on the surface of a plane, no three of which intersect at a common point. He counts many triangles, but how many of them contain no triangles with a strictly smaller area?


1 \le N \le 500

|x_i|, |y_i| \le 2 \cdot 10^3

All lines are pairwise distinct.

No three lines intersect at a common point.

Input Specification

The first line contains a single positive integer, N.

The next N lines contain four space-separated integers, x_1, y_1, x_2, y_2, indicating a line going through distinct points (x_1, y_1) and (x_2, y_2).

Output Specification

Output the number of such triangles.

Sample Input

0 0 0 10
0 0 10 0
0 5 5 5
0 10 10 0

Sample Output



There are no comments at the moment.