Editorial for Mock CCC '19 Contest 2 S3 - Tudor Tallies Triangular Totals - Olympiads Online Judge

Editorial for Mock CCC '19 Contest 2 S3 - Tudor Tallies Triangular Totals

Remember to use this editorial 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.

To solve the subtask, every line must contain at least two points, but there are $\mathcal O(N^2)$ $O (N^{2})$ possible lines that contain at least two points, so try all of them. It takes $\mathcal O(N)$ $O (N)$ to check if every point lines on the line, giving an $\mathcal O(N^3)$ $O (N^{3})$ algorithm.

For full credit, fix one point and consider all lines that one can draw which go through that point and one other point. There are only $\mathcal O(N)$ $O (N)$ of them - furthermore there is a clear mapping from point to line which needs to be drawn, so the number of points that lie on every line can be enumerated in $\mathcal O(N)$ $O (N)$ . Remove the point and repeat, for an $\mathcal O(N^2)$ $O (N^{2})$ algorithm.

Comments

There are no comments at the moment.