### SRM 686, D2, 500-Pointer (SegmentsAndPoints)

### James S. Plank

Mon Oct 10 00:50:03 EDT 2016

This is one of those problems where you need to do things in the correct order.
I suspect that the low scores came from topcoders who didn't have enough time to
solve the problem.
Let's suppose that we go through the points in **p** from smallest to largest.
And let's suppose we're looking at the first point. This will be the smallest point
in **p**. We want to match it with a segment, and if there are multiple segments
that could match, we have to choose one of them to match. We'd like to do that in
the way that makes things best for the rest of the points.

Here's my idea of how to choose the segment -- choose the one that has the smallest **r**
value. That is the segment that is going to be the least useful for subsequent **p**
values.

Now, the constraints on this one are so small that you use pretty much whatever algorithm
you want to solve it. I sorted **p**, and then added a vector called **done**,
which I set to all zeros. For each value in **p**, I ran through **l** and **r**,
and found the segment with the smallest value of **r**, such that:

- The segment contained my point in
**p**.
- The segment's
**done** value equalled 0.

If there was no such segment, I returned "Impossible." Otherwise, I set the segment's
**done** value to 1. If I got to the end of **p**, I returned "Possible."
That algorithm is *O(n*^{2}), where *n* is the size of **p**,
**l** and
**r**.

**My solution**