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)$ ~\mathcal O(N^2)~ possible lines that contain at least two points, so try all of them. It takes $\mathcal O(N)$ ~\mathcal O(N)~ to check if every point lines on the line, giving an $\mathcal O(N^3)$ ~\mathcal 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)$ ~\mathcal 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)$ ~\mathcal O(N)~. Remove the point and repeat, for an $\mathcal O(N^2)$ ~\mathcal O(N^2)~ algorithm.

Comments

There are no comments at the moment.