Header Ads Widget

Library problems | Hackerearth solution

 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 , and there are  tables in the library and the  table is positioned at point (,). 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 (), 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 () in the plane, such that for each given point (,), there exists a chosen point at a distance of at most .

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

Input format

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

Output format

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

Constraints
15×103
1109
105,105

Note: Assume that point  is at a distance of at most  from point , if (,)106 and here,  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.

Code(C++):-


#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
}
 
int main() {
    int n, r;
    cin >> n >> r;
 
    vector<pair<int,int>> tables(n);
    for(int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        tables[i] = make_pair(x, y);
    }
 
    sort(tables.begin(), tables.end());
 
    vector<bool> marked(n, false);
    int count = 0;
    vector<pair<int,int>> lights;
 
    for(int i=0; i<n; i++) {
        if(!marked[i]) {
            count++;
            marked[i] = true;
            lights.push_back(tables[i]);
            for(int j=i+1; j<n; j++) {
                if(!marked[j] && dist(tables[i].first, tables[i].second,
tables[j].first, tables[j].second) <= r) {
                    marked[j] = true;
                }
            }
        }
    }
 
    cout << count << endl;
    for(int i=0; i<count; i++) {
        cout << lights[i].first << " " << lights[i].second << endl;
    }
 
    return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Post a Comment

0 Comments