Header Ads Widget

Library problems | Hackerearth solution

Rajnish Tripathi 19:45

 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
1≤�≤5×103
1≤�≤109
−105≤��,��≤105

Note: Assume that point � is at a distance of at most � from point �, if ��������(�,�)−�≤10−6 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:-

Tags:

Post a Comment

0 Comments