Library problems

0

0 votes
Geometry, Line Sweep Technique, C++, Math
Problem

A university's library has been having electricity issues and students have been struggling to study during nights. They have filed a lot of complaints about it. Finally, after finding a good deal on a lighting option, the university decided to fix the issue.

Each light source can illuminate a circle with a radius of r, and there are n tables in the library and the ith table is positioned at point (xi,yi). Since the university wants to minimize it's expenses, they want to buy the minimum number of light sources. You have to help the university find the minimum number of light sources (k), such that each table is illuminated by at least 1 light source.

In other words, your task is to select a minimum number of points (k) in the plane, such that for each given point (xi,yi), there exists a chosen point at a distance of at most r.

Note: You can place more than one light source at a specific point.

Input format

  • The first line contains integers n and r respectively.
  • In each of the next n lines, there are two integers representing xi and yi respectively that display the position of the ith table.

Output format

  • In the first line of output, print an integer k that represents the number of light sources.
    • Note that the equation kn must hold.
  • In each of the next k lines, print two decimal numbers representing xi,yi respectively that shows the location of the ith light source.
    • Note that the equation |xi,yi|109 must hold.

Constraints
1n5×103
1r109
105xi,yi105

Note: Assume that point p is at a distance of at most r from point q, if distance(p,q)r106 and here, distance represents Euclidean distance.

Sample Input
4 2
0 2
0 4
2 0
2 4
Sample Output
3
0 2
2 0
2 4
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In this sample, we place 3 light sources at points (0,2), (2,0) and (2,4). As you can see in the picture below, these points cover all the given points.

However, this answer is not the best possible. You can see that if we place 2 light sources at (1,1) and (1,3), it would also cover all the given points.

Editor Image

?