Acute Triangles

Interview

Time limit2sMemory limit1024 MB

Summary

Given N integer points (N up to 200), count the acute triangles they form, and how many of those are pairwise non-congruent.

Level: Medium5 of 10
Topics: Geometry, Sorting, Hash map
Solved: No attempts yet

Problem

A triangle is the part of a plane, including its boundary, bounded by the segments that connect three distinct points. These segments are the sides of the triangle. Two triangles are equal if they consist of the same points. They are congruent if one can be obtained from the other by a rigid motion (translation, rotation, or reflection). The congruence criteria from elementary geometry are KKK, KNK, and NKN, where K denotes a side and N denotes an angle. So the criteria are side-side-side, side-angle-side, and angle-side-angle. A triangle is called acute if all of its interior angles are acute.

Write a program that reads the coordinates of $N$ points and finds:

How many distinct (mutually non-equal) acute triangles have their vertices at the given points?
How many mutually non-congruent acute triangles have their vertices at the given points?

Input

The first line of the input file contains the number of points $N$ ( $3 \le N \le 200$ ). Each of the next $N$ lines contains two integers separated by a space, $X$ and $Y$ ( $0 \le X \le 100$ , $0 \le Y \le 100$ ), the coordinates of one point. You may assume that the points are pairwise distinct.

Output

The first line of the output file contains the total number of distinct acute triangles. The second line contains the number of mutually non-congruent acute triangles.

Examples1

Example 1
Input
```
5
0 0
2 0
4 0
1 2
3 2
```
Expected output
```
5
2
```