Editorial for DMOPC '16 Contest 1 P2 - Lines - Olympiads Online Judge

Editorial for DMOPC '16 Contest 1 P2 - Lines

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.

Authors: Phoenix1369, jimgao

Knowledge required: simple math

For $90\%$ $90 %$ of the marks, a brute-force algorithm which iterates over every pair of lines while keeping a counter is sufficient.

For the final $10\%$ $10 %$ of the marks, it is important to note that any two lines which do not share a slope must intersect eventually.

The exact implementation is left as an exercise to the reader.

Time Complexity: $\mathcal{O}(N \log N)$ $O (N \log N)$

Comments

There are no comments at the moment.