# HackerEarth Cross the river problem solution

In this HackerEarth Cross the river problem solution You are required to cross a river to reach your destination. The streamflow of the river was fast, therefore, you cannot cross the river by swimming.

The river is available at the X-axis and its boundary is marked by Y coordinates, from y = A to y = B.

------------------------------------------------------------------------------- (y = A)

..................................................................................................

..................................................................................................

..................................................................................................

-------------------------------------------------------------------------------- (y = B)

You are provided with some rocks along with their centers and radius respectively. Currently, you are standing on the shore y = B. You cannot jump between rocks but can move from one rock to another if both rocks overlap at some point. You are required to determine whether you will be able to cross the river by using rocks or not. If you can cross the river, then print the minimum number of rocks that are required to cross the river. Otherwise, print -1.

## HackerEarth Cross the river problem solution.

`#include<bits/stdc++.h>using namespace std;#define TRACE#ifdef TRACE#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)template <typename Arg1>void __f(const char* name, Arg1&& arg1){  cerr << name << " : " << arg1 << std::endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}#else#define TR(...)#endiftypedef long long               LL;typedef pair<int,int>           II;typedef vector<int>             VI;typedef vector<II>              VII;#define REP(i,i1,n)             for(int i=i1;i<n;i++)#define REPB(i,i1,n)            for(int i=i1;i>=n;i--)#define PB                      push_back#define MP                      make_pair#define ALL(c)                  (c).begin(),(c).end()#define F                       first#define S                       second#define log2                    0.30102999566398119521373889472449L#define SZ(a)                   (int)a.size()#define EPS                     1e-12#define MOD                     1000000007#define FAST_IO                 ios_base::sync_with_stdio(false);cin.tie(NULL)#define SI(c)                   scanf("%d",&c)#define SLL(c)                  scanf("%lld",&c)#define PIN(c)                  printf("%d\n",c)#define PLLN(c)                 printf("%lld\n",c)#define N                       200010#define endl                    '\n'#define FILL(ar,vl)             for(int i=0;i<N;i++)ar[i]=vl#define FILL2(ar,vl)            for(int i=0;i<N;i++)for(int j=0;j<N;j++)ar[i][j]=vlinline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }//--------------------------MAIN CODE STARTS HERE----------------#define MAX 1e9int main() {      int T;    SI(T);    while(T--) {        int A, B, n;        SI(n);        int X[n], Y[n], R[n], vis[N], mark_1[n], mark_2[n], dist[n];        memset(vis,0,sizeof(vis));        memset(mark_1,0,sizeof(mark_1));        memset(mark_2,0,sizeof(mark_2));        vector<int> g[n];        for(int i = 0; i < n; i ++) {            SI(X[i]);SI(Y[i]);SI(R[i]);        }        SI(A);SI(B);        for(int i = 0; i < n ; i ++) {            for(int j = i + 1; j < n; j ++) {               LL dist_1 = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);               LL dist_2 =(R[i] + R[j]) * (R[i] + R[j]);               if(dist_1 <= dist_2) {         // constructing edge between overlapping rocks                    g[i].push_back(j);                    g[j].push_back(i);               }            }        }        // checking which of the rocks overlap with the shore (y=a) && (y=b)        for(int i = 0; i < n; i++) {            if(abs(Y[i] - A) <= R[i]) mark_1[i] = 1;            if(abs(Y[i] - B) <= R[i]) mark_2[i] = 1;        }        priority_queue< II,vector<II>,greater<II> > Q;        for(int i = 0; i < n; i++) dist[i] = MAX;        for(int i = 0; i < n; i++) {            if(mark_2[i]) {                Q.push(MP(1,i));                dist[i] = 1;            }        }        int ans = MAX;        while(!Q.empty()) {            II idx = Q.top();            int cost = idx.first, id = idx.second;            Q.pop();            if(vis[id]) continue;            vis[id] = 1;            if(mark_1[id]) {                ans = min(ans,cost);            }            for(int i = 0; i < g[id].size(); i ++) {                if(dist[g[id][i]] > cost + 1) {                    dist[g[id][i]] = cost + 1;                    Q.push(MP(cost + 1,g[id][i]));                }            }        }        if(ans!=MAX)            PIN(ans);        else PIN(-1);    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define piii pair<int,pair<int,int> >#define pii pair<int,int>#define mkp make_pair#define fi first#define se second#define sfd(n) scanf("%d",&n)#define MAXX 1000000000#define MINX -1000000000using namespace std;pair<pair<int,int>,int> pt[5005];vector<int> adj[5005];int s,d;int up[5005],down[5005];queue<int> q;bool Intersects(int x1,int y1,int r1,int x2,int y2,int r2){    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(r1+r2)*(r1+r2);}void bfs(int arr[]){    while(!q.empty())    {        int k=q.front();        q.pop();        int a=pt[k].fi.fi;        int b=pt[k].fi.se;        for(int j=0;j<adj[k].size();j++)        {            if(arr[adj[k][j]]>arr[k]+1)            {                arr[adj[k][j]]=arr[k]+1;                q.push(adj[k][j]);            }        }    }}int main(){    int t;    sfd(t);    assert(1<=t&&t<=10);    while(t--)    {        int n;        sfd(n);        assert(1<=n&&n<=5000);        for(int i=0;i<n;i++)        {            int x,y,r;            sfd(x);            sfd(y);            sfd(r);            assert(MINX<=x&&x<=MAXX);            assert(MINX<=y&&y<=MAXX);            assert(1<=r&&r<=MAXX);            pt[i]=mkp(mkp(x,y),r);        }        sfd(s);        sfd(d);        assert(MINX<=s&&s<=MAXX);        assert(MINX<=d&&d<=MAXX);        assert(s>=d);        for(int i=0;i<n;i++)        {            adj[i].clear();            up[i]=INT_MAX;            down[i]=INT_MAX;        }        for(int i=0;i<(n-1);i++)        {            for(int j=i+1;j<n;j++)            {                if(Intersects(pt[i].fi.fi,pt[i].fi.se,pt[i].se,pt[j].fi.fi,pt[j].fi.se,pt[j].se))                {                    adj[i].push_back(j);                    adj[j].push_back(i);                }            }        }        for(int i=0;i<n;i++)        {            if(pt[i].fi.se-pt[i].se<=d)            {                up[i]=1;                q.push(i);            }        }        bfs(up);        for(int i=0;i<n;i++)        {            if(pt[i].fi.se+pt[i].se>=s)            {                down[i]=1;                q.push(i);            }        }        bfs(down);        int ans=INT_MAX;        for(int i=0;i<n;i++)        {            if(up[i]!=INT_MAX && down[i]!=INT_MAX)                ans=min(ans,up[i]+down[i]-1);        }        if(ans==INT_MAX)            printf("-1\n");        else            printf("%d\n",ans);    }}`