fork(3) download
copy 
  1. // https://w...content-available-to-author-only...t.com/problems/valid-path/
  2.  
  3.  
  4. #include<bits/stdc++.h>
  5. #include<unordered_set>
  6. using namespace std;
  7.  
  8. class Solution{
  9. public:
  10.     string solve(int A, int B, int C, int D, vector<int> &E, vector<int> &F);
  11. };
  12.  
  13. #define pii pair<int,int>
  14.  
  15. int par[1000+5];
  16. int rnk[1000+5];
  17. bool vis[1000+5];
  18.  
  19. void initialise(){
  20.     for(int i=0;i<=1000;i++){
  21.         par[i]=i;
  22.         rnk[i]=1;
  23.         vis[i]=false;
  24.     }
  25. }
  26.  
  27. int findPar(int node){
  28.     if(par[node]==node)return node;
  29.     return par[node]=findPar(par[node]);
  30. }
  31.  
  32. void makeUnion(int a,int b){
  33.     int parA=findPar(a);
  34.     int parB=findPar(b);
  35.  
  36.     if(parA==parB)return;
  37.     if(rnk[parA]<rnk[parB])par[parB]=parA;
  38.     else if(rnk[parB]<rnk[parA])par[parA]=parB;
  39.     else{
  40.         rnk[parA]++;
  41.         par[parB]=parA;
  42.     }
  43. }
  44.  
  45.  
  46. bool findBlockage(int root,int X,int Y,int N,int R,vector<pair<int,pii>>vec){
  47.     int top=0;
  48.     int bottom=INT_MAX;
  49.     int left=INT_MAX;
  50.     int right=0;
  51.  
  52.     for(int i=0;i<N;i++){
  53.         if(par[vec[i].first]==root){
  54.             int x=vec[i].second.first;
  55.             int y=vec[i].second.second;
  56.             top=max(top,y+R);
  57.             bottom=min(bottom,y-R);
  58.             left=min(left,x-R);
  59.             right=max(right,x+R);
  60.         }
  61.     }
  62.     if(top>=Y and bottom<=0)return true;
  63.     if(right>=X and left<=0)return true;
  64.     if(top>=Y and right>=X)return true;
  65.     if(left<=0 and bottom<=0)return true;
  66.     return false;
  67. }
  68.  
  69. string Solution::solve(int X, int Y, int N, int R, vector<int> &E, vector<int> &F) {
  70.     vector<pair<int,pii>> vec;
  71.     int id=0;
  72.     for(int i=0;i<N;i++){
  73.         vec.push_back({id,{E[i],F[i]}});
  74.         id++;
  75.     }
  76.  
  77.     initialise();
  78.  
  79.     for(int i=0;i<N;i++){
  80.         for(int j=i;j<N;j++){
  81.             if(i==j)continue;
  82.             int x1=vec[i].second.first;
  83.             int x2=vec[j].second.first;
  84.  
  85.             int y1=vec[i].second.second;
  86.             int y2=vec[j].second.second;
  87.  
  88.             if(((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) <= (4*R*R)){
  89.                 makeUnion(vec[i].first,vec[j].first);
  90.             }
  91.         }
  92.     }
  93.  
  94.     for(int i=0;i<N;i++){
  95.         if(!vis[par[vec[i].first]]){
  96.             vis[par[vec[i].first]]=1;
  97.             bool ret = findBlockage(par[vec[i].first],X,Y,N,R,vec);
  98.             if(ret)return "NO";
  99.         }
  100.     }
  101.     return "YES";
  102. }
  103.  
  104. int main(){
  105.     int n,x,y,r;
  106.     cin>>x>>y>>n>>r;
  107.     vector<int>X(n);
  108.     vector<int>Y(n);
  109.  
  110.     for(int i=0;i<n;i++)cin>>X[i];
  111.     for(int i=0;i<n;i++)cin>>Y[i];
  112.  
  113.     Solution sol;
  114.     cout<<sol.solve(n,x,y,r,X,Y)<<endl;
  115. }
  116.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
3 2 2 1
1 2
1 1
stdout
copy 
NO
https://ideone.com/19iSOn
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!