## Editorial for UHCC1 P5 - Binary Triangles

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

Precompute the distance between each pair of points, this takes time , then bruteforce all 3-tuples and check if they form a triangle. This solution has time complexity which is within the constraints.

#### Subtask 2

First notice that you can completely ignore the square root in the distance formula as it makes no difference. Since all coordinates are binary, we can replace the square of the difference with absolute value of the difference, for . This distance formula counts exactly the number of coodinates that are different given two points. Now if we write the coordinates as a binary integer, mark the bit to if the coodinate is . Then we recognize the distance formula as taking the bitwise XOR of the two integers and count the number of bits.

The precomputation process can be optimized using bitset XOR and popcount, reducing the time from to . This solution has time complexity which is within the constraints.

## Comments

bitset

bitset