Circles in a Rectangles

general
1

What can the possible approach be for the problem stated below? I thought of marking the contour of all the circles in x*y maze, but that seems to be complex. Can there be any better approach?

There is a rectangle with left bottom
as (0, 0) and right up as (x, y).
There are n circles such that their
centres are inside the rectangle.
Radius of each circle is r. Now we
need to find out if it is possible
that we can move from (0, 0) to (x, y)
without touching the circle. We can
move freely anywhere.

2

your question goes here (on interviewbit.com)
Valid Path | InterviewBit

solution approach is to basically find the blockage by every circle combined.
also take care of intersecting circles.
if two circles center are less than 2*r apart, they are intersecting circles.

code for above question on interviewbit

#include<unordered_set>
#define pii pair<int,int>

int par[1000+5];
int rnk[1000+5];
bool vis[1000+5];

void initialise(){
    for(int i=0;i<=1000;i++){
        par[i]=i;
        rnk[i]=1;
        vis[i]=false;
    }
}

int findPar(int node){
    if(par[node]==node)return node;
    return par[node]=findPar(par[node]);
}

void makeUnion(int a,int b){
    int parA=findPar(a);
    int parB=findPar(b);
    
    if(parA==parB)return;
    if(rnk[parA]<rnk[parB])
        par[parB]=parA;
    else if(rnk[parB]<rnk[parA])
        par[parA]=parB;
    else{
        rnk[parA]++;
        par[parB]=parA;
    }
}


bool findBlockage(int root,int X,int Y,int N,int R,vector<pair<int,pii>>vec){
    int top=0;
    int bottom=INT_MAX;
    int left=INT_MAX;
    int right=0;

    for(int i=0;i<N;i++){
        if(par[vec[i].first]==root){
            int x=vec[i].second.first;
            int y=vec[i].second.second;
            top=max(top,y+R);
            bottom=min(bottom,y-R);
            left=min(left,x-R);
            right=max(right,x+R);
        }
    }
    if(top>=Y and bottom<=0)return true;
    if(right>=X and left<=0)return true;
    if(top>=Y and right>=X)return true;
    if(left<=0 and bottom<=0)return true;
    return false;
}

string Solution::solve(int X, int Y, int N, int R, vector<int> &E, vector<int> &F) {
    vector<pair<int,pii>> vec;
    int id=0;
    for(int i=0;i<N;i++){
        vec.push_back({id,{E[i],F[i]}});
        id++;
    }

    initialise();

    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            if(i==j)continue;
            int x1=vec[i].second.first;
            int x2=vec[j].second.first;
            
            int y1=vec[i].second.second;
            int y2=vec[j].second.second;
            
            if(((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) <= (4*R*R)){
                makeUnion(vec[i].first,vec[j].first);
            }
        }
    }

    for(int i=0;i<N;i++){
        if(!vis[par[vec[i].first]]){
            vis[par[vec[i].first]]=1;
            bool ret = findBlockage(par[vec[i].first],X,Y,N,R,vec);
            if(ret)return "NO";
        }
    }
    return "YES";
}
3

An you have the centers of the circles or not?

4

Yes, I have

5

You have a link to full statement?

6

Round2, Q2: http://www.geeksforgeeks.org/directi-interview-set-5-campus/

1 Like