Submit | All submissions | Best solutions | Back to list |
TAP2014C - Constellation of the parallelogram |
[The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ]
One morning, when Cyrus Samsa woke from troubled dreams, he found himself lying on his bed, but not transformed into a monstrous insect. However, when he looked up at the still starry sky, he found that the visual setting of the cosmos showed four stars positioned as the vertices of a perfect parallelogram. Being a big geometry enthusiast, he called those four stars "constellation of the parallelogram".
A parallelogram is a four-sided polygon with its pairs of opposite sides being of identical length. Equivalently, a parallelogram is a convex quadrilateral whose diagonals intersect at their midpoints. The following figure illustrates both definitions, for a parallelogram with sides of lengths L and l, and diagonals of lengths D and d.
Unfortunately, astronomers still do not agree on which were the stars that Cyrus was looking at. The problem is that on each image obtained of the sky's configuration, there are usually many sets comprising four stars that are the vertices of a parallelogram.
A starry sky is represented on an image as a set of points in the Cartesian plane, each of them corresponding to a star. The following figure shows three copies of the same image, each illustrating one of the three sets of four stars which are the vertices of a parallelogram, which are marked in the figure with solid lines.
Your task is to safeguard the good name of astronomers by calculating, given an image, the number of parallelograms contained in it.
Input
The first line contains an integer N indicating the number of stars on the image to be analyzed (4 ≤ N ≤ 1000).
The following N lines describe each of the stars on the image with two integers Xi and Yi, indicating respectively the X and Y coordinates of the star on the Cartesian plane (-108 ≤ Xi, Yi ≤ 108 for i = 1, 2, ..., N). You may assume that no two stars on the image are on the same position.
Output
Print a single line containing a single integer representing the number of sets of four points on the input image that are the vertices of a parallelogram.
Example 1
Input: 7 0 1 1 3 2 4 3 1 4 2 4 3 5 0 Output: 3
Example 2
Input: 11 0 0 0 1 0 -1 1 0 1 1 1 -1 -1 0 -1 1 -1 -1 0 2 1 2 Output: 44
Example 3
Input: 4 0 0 0 1 0 2 0 3 Output: 0
Example 4
Input: 6 -100000000 100000000 100000000 -100000000 -100000000 -100000000 100000000 100000000 1 1 -1 -1 Output: 2
Added by: | Fidel Schaposnik |
Date: | 2014-09-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Argentinian Programming Tournament 2014 |
hide comments
2021-07-21 17:23:51
The original problem link gives 404 page not found. |
|
2021-07-21 17:18:47
The judge throws 38 test files at the submission. Last edit: 2021-07-22 15:54:39 |