Oblongs and Right Triangles
InterviewTime limit1sMemory limit256 MB
Count 4-black-point sets forming a non-square rectangle and 3-white-point sets forming a right triangle, disjoint and with positive area.
- Level
Medium6 of 10
- Topics
- Brute force, Geometry, Combinatorics, Math
- Solved
- No attempts yet
Problem
There are N points on the plane; the i-th point is at (Xi, Yi). Multiple points may occupy the same location. Four of the points are coloured black and three other points are coloured white. The remaining N − 7 points are left uncoloured.
An oblong is a rectangle that is not a square.
A right triangle is a triangle in which one interior angle is exactly ninety degrees.
Determine the number of ways to colour the points such that the four black points are the vertices of an oblong and the three white points are the vertices of a right triangle. Both shapes must have positive area.
Input
Line 1 contains one integer N (7 ≤ N ≤ 24).
Line 2 contains N integers X1, ..., XN (−229 ≤ Xi ≤ 229).
Line 3 contains N integers Y1, ..., YN (−229 ≤ Yi ≤ 229).
Output
Print one line with one integer, the number of ways to choose an oblong and a right triangle.
Hint
The only way to form an oblong is with points 1, 2, 7, and 8. Of the remaining four points, there are two ways to form a right triangle from them.
