CF97B Superset

A set of points on a plane is called good, if for any two points at least one of the three conditions is true: - those two points lie on same horizontal line; - those two points lie on same vertical line; - the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points. You are given a set consisting of $ n $ points on a plane. Find any good superset of the given set whose size would not exceed $ 2·10^{5} $ points.

N/A

N/A