Hipercampo
InterviewTime limit1sMemory limit1024 MB
Given two anchors on the x-axis and N points above, choose the largest subset whose segments to both anchors meet only at the anchors.
- Level
Medium6 of 10
- Topics
- Geometry, Sorting, Dynamic programming, Intervals
- Solved
- No attempts yet
Problem
You are given two anchors, the points and with , which form a horizontal segment. You are also given a set of points with and . The leftmost picture below is one possible input.

To connect a point you draw both segments and . You want to connect several points, but the drawn segments must meet only at the anchors. Points 1 and 4 in the middle picture cannot both be connected, because their segments would cross somewhere other than an anchor. The rightmost picture shows that points 8, 5 and 3 can be connected together, with the segments meeting only at the anchors.
Compute the largest number of points that can be connected so that the segments meet only at the anchors.
Input
The first line contains three integers (), and (). is the number of points in the set , and and are the coordinates of the anchors and . Each of the next lines contains two integers and (), the coordinates of the th point, for . No two points share a position, and there are no two distinct points and such that is collinear or is collinear.
Output
Print one line with one integer, the largest number of points of that can be connected so that the segments meet only at the anchors.