### PROBLEM LINK:

**Author:** Kamil Debowski

**Tester:** Niyaz Nigmatullin

**Editorialist:** Kamil Debowski

### DIFFICULTY:

MEDIUM-HARD

### PREREQUISITES:

none

### PROBLEM

The task is to generate such N (N ≤ 10) points with non-negative coordinates up to 10^{6}, that each triple of points would be **mistakenly** treated as coolinear by the following function, that makes all computations modulo 2^{32}:

```
typedef unsigned int UI;
bool areCollinear(UI ax, UI ay, UI bx, UI by, UI cx, UI cy) {
return (bx - ax) * (cy - ay) == (by - ay) * (cx - ax);
}
```

### EXPLANATION

Let’s think about any general equality A * B == C * D.

Let’s say we want this equality to be true modulo some value X, but false without modulo.

So A * B and C * D should be different but their remainders should be the same.

Trying random numbers won’t work for big X because the probability of getting equal remainders is very low.

But we must notice that X is some special numbers in this problem — it’s equal to 2^{32}.

The main part of this problem is to get the idea that it’s easy to make numbers A * B and C * D divisible by 2^{32}.

If we want A, B, C, D to be quite small (not exceeding 10^{6}), we can say that each of those four numbers is of form k * 2^{16} for some k.

In other words, each of them is divisible by 2^{16} = 65536.

Then both A * B and C * D are divisible by 2^{32} so obviously they are equal modulo 2^{32}.

In the given problem about points we will try to find such points that all their coordinates are divisible by 2^{16}.

This ensures that we satisfy all equalities modulo 2^{32}, because for all triples of points we have (bx - ax) * (cy - ay) mod 2^{32} = 0.

The remaining thing is that the points can’t be collinear.

So, we want each point to be of form (x_{i} * 2^{16}, y_{i} * 2^{16}) and we need to find N points that none three of them are collinear.

We can say that we just need pairs (x_{i}, y_{i}) where x_{i}, y_{i} ≤ 10^{6} / 2^{16} ≈ 15.

We are looking for N points with coordinates up to 15, such that none three of them are collinear.

At the end we will multiply their coordinates by 2^{16} and print them.

Since N ≤ 10, we can just find 10 such points on paper.

For example, I found points that form the convex shape (the parabola) so they must be non-collinear: (0,0), (1,5), (2,9), (3,12), (4,14), (5,15), (6,14), (7,12), (8,9), (9,5).

The alternative approach is to generate random points and check if they aren’t collinear — in such a case try again, and so on, till you find the valid set of points.

Yet another approach is used in the tester’s code — it uses the fact for for any prime P points (i, i * i % P) aren’t collinear, so we can say that P = 13 and generate 13 points this way.