CareerCup

It sounds to me like a problem solvable by circle-circle and circle-line-segment intersection. Consider the rectangle's 4 sides: (L)eft, (T)op, (R)ight, (B)ottom. If you can establish that there is a "chain" of intersecting circles that connects L-B, T-B, T-R or L-R then there is a blockade which prevents travel from the lower left corner to the top right. The chain can be a single circle intersecting two relevant sides, or a long chain of intersecting circles. Chains from L-to-T or B-to-R can't block the path if those are the only sides they touch.

I haven't written an algorithm to solve this, just thought about it for a couple minutes, but I would expect it to be O(n^2) worst case runtime (long chain of all n circles, n^2 circle-circle tests), O(n) best case to prove there is a path if in one pass over all circles you find that none intersect the rectangle, and O(1) best case to find there is no path, since you could discover on your very first inspection a circle that makes a blocking connection between 2 sides.

Thinking outside the box :-) as your problem definition does not specify such a limitation you can just go around the outside. Assuming 0,0 and X,Y are not themselves in circles you should be able to make it. That will take O(n) to check.

I would assume you are not allowed to go outside the box though.

Create a graph in the following way:
If 2 centers are less then 2r apart then they are connected.
Also if a center is less then r from the (top or the left side) link it to a point called A
Additionally if a center is less then r from the (bottom or the right side) it gets connected to a point we will call B
If you can get from point A to point B in the graph then you are blocked.

This will take O(n^2) distance computations and then you have to run through the graph but you can optimize it.

Obviously don’t do the in range computation as r*2 >= sqrt((x1-x2)^2 + (y1-xy)^2)
But rather (r*2)^2 >= (x1-x2)^2 + (y1-xy)^2 you could even compute a NY distance before escalating to the real distance

1) Put all the centers into some kind of two dimensional spatial data structure. If you have lots of memory this can be a matrix of variable length vectors. But if your memory is limited you could use a hash table that is indexed by the combination of 2 keys X and Y. For a given cell you may get a number of points. You will need to consider there connectedness. If the cells are small enough (less then 2r in diagonal) you just mark these as connected. They you need to see which centers in the current cell are connected to centers in the adjoining ones. You might even consider rehashing the local cells temporarily .

2) if the data is sparse we might analyze the two dimensional spatial data structure to eliminate many of the cells from consideration.

3) Rather than first building the graph and then searching it you can build it on the fly starting from the top and left edges. Then as you work you can even optimize your search with the A* algorithm, starting with points closest to the corners. The distance estimate can be derived from just the distance two the lower or right edges or we might also get this from an analysis of the two dimensional spatial data structure.

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;

class Solution{
public:
string solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F);
};

#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";
}

int main(){
int n,x,y,r;
cin>>x>>y>>n>>r;
vector<int>X(n);
vector<int>Y(n);

for(int i=0;i<n;i++)cin>>X[i];
for(int i=0;i<n;i++)cin>>Y[i];

Solution sol;
cout<<sol.solve(n,x,y,r,X,Y)<<endl;
}