# ACM Collegiate Programming Contest: Blue Balloon Parallelogram counting [closed]

The problem is from the ACM Collegiate Programming Contest: 5924 - Parallelogram Counting

Problem Description

The International Consortium for Parallelogram Counting (ICPC) wants to move into the digital age and automate their parallelogram counting. They want to count the number of parallelograms formed by universities in various countries. For each country, they have a map which is divided into a regular n × n grid. In each cell of the grid, they have indicated whether a university is present or not (there are never two universities in the same grid cell).

After some argument, they have settled on the following definition of a parallelogram: it is a set of four distinct points (A, B, C, D), such that AB and CD are parallel and have the same length. Note that a parallelogram can have zero area. Two parallelograms are considered different if one contains a point that the other does not; simply considering the same four points in a different order does not make a new parallelogram.

Input

Input consists of multiple test cases, each describing a country.

Each case begins with a line containing the integer n (1 ≤ n ≤ 500), the size of the grid. This is followed by n lines of n characters. Each character is either a ‘1’ to indicate that a university is present, or a ‘0’ to indicate that no university is present, in the corresponding grid cell. There are no spaces between the characters.

The last case is followed by a line containing ‘-1’, equivalent to n == −1. There will be at most three test cases in which n > 20.

Output

For each country, output a line containing the number of parallelograms formed by universities in that country. Note that this number might be large.

Input  4 1101 1000 0001 0011 4 1111 0000 0000 1111 3 111 111 111 -1 

Sample Output  3 16 22 

I've been able to parse the input and create an array for each country, but I can't seem to understand how they calculate the number of parallelograms formed.

• We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael
Sep 23, 2018 at 11:32
• Note that programming is offtopic here.
– Raphael
Sep 23, 2018 at 11:32
• It's clearly not off-topic. If you read the post, what I was asking for was if anyone could figure out how the parallelograms were counted, the programming is not what I'm asking for. It was stated that parallelograms have 4 distinct points, but having an input of 3x3 the output was 22.
– Jsph
Sep 23, 2018 at 13:24
• @Apass.Jack Thanks for the explanation, I was really having difficulty at understanding how the parallelograms were formed.
– Jsph
Oct 2, 2018 at 6:42

For better visualization, I use "." instead of "0" to indicate that no university is present.

The first test case in the sample input has 3 admissible parallelograms.

1101      11..   1...   .1..
1000      ....   1...   1...
0001      ....   ...1   ...1
0011      ..11   ...1   ..1.


The second test case in the sample input has 16 admissible parallelograms.

1111      1111   ....   11..   11..   11..   .11.   .11.   .11.
0000      ....   ....   ....   ....   ....   ....   ....   ....
0000      ....   ....   ....   ....   ....   ....   ....   ....
1111      ....   1111   11..   .11.   ..11   11..   .11.   ..11

..11   ..11   ..11   1.1.   1.1.   .1.1   .1.1   1..1
....   ....   ....   ....   ....   ....   ....   ....
....   ....   ....   ....   ....   ....   ....   ....
11..   .11.   ..11   1.1.   .1.1   1.1.   .1.1   1..1


The third test case in the sample input has 22 admissible parallelograms.

111    11.   11.   11.   11.   .11   .11   .11   .11   ...   ...   ...
111    11.   .11   ...   ...   11.   .11   ...   ...   11.   11.   .11
111    ...   ...   11.   .11   ...   ...   11.   .11   11.   .11   11.

...   1.1   1.1   ...   .1.   1..   ..1   1..   .1.   .1.   .1.
.11   1.1   ...   1.1   1.1   1.1   1.1   11.   11.   .11   .11
.11   ...   1.1   1.1   .1.   ..1   1..   .1.   1..   ..1   ..1


For $$n\le6$$, a brute-force search is able to calculate the number of parallelograms within a second. For example, a 6x6 grid of all "1"s has 2273 parallelograms. The search iterates through all possible combination of 4 cells. For each 4 cells, check if they are distinct and each of them stores "1" and they can form a parallelogram. If not, skip. If yes, add them to the result set. This result set is initialized as an empty set before the brute force begins. Two parallelograms are consider the same if and only if their four points are the same as sets. To speed up the comparison of two parallelograms, the four cells of a parallelogram are always sorted in the lexicographical order. Then two parallelograms are the same if and only if they have the same first, second, third and fourth cell. This simple algorithm by brute-force search is meant to be the correct algorithm whose result can be used to verify the result of more complicated algorithm in the small cases. Apparently, to finish the actual task, a much faster algorithm must be developed.