CareerCup

Build a graph with rocks as vertices, with edges representing overlaps between rocks.To find overlap between rocks use this code

bool Overlap(float x1,float y1,float r1,float x2,float y2, float r2)
{
    if((pow((x2-x1),2)+pow((y2-y1),2))<(r1+r2))
		return true;
	else
	    return false;

}

Add source and destination vertices.Source vertex is connected to the "shore rocks" of
one shore. Destination vertex is connected to the "shore rocks" of other shore. Use this code to find shore rocks

bool ShoreRock( float rockX,float rockY, float rockR, float yIntercept)
{
	    if(((rockY-yIntercept)-rockR)>0)
			return true;
		else
			return false;

}

Now we got a graph, we have to find shortest path from source to destination. We can use djikstra algorithm for this.

import java.util.*;

public class RockProblem{
	public static void main(String[] args){
		int shore_b = 3; 
		int shore_a = 0; 
		List<Rock> rockList = new ArrayList<Rock>();
		rockList.add(new Rock(1, 1, 1, 1, shore_a, shore_b));
		rockList.add(new Rock(2, 1, 2, 1, shore_a, shore_b));
		rockList.add(new Rock(3, 3, 4, 1, shore_a, shore_b));
		solve(rockList, shore_a, shore_b);
	}
	public static void solve(List<Rock> rockList, int shore_a, int shore_b){
		Path path = null;
		for(Rock r: rockList){
			if(r.touchShoreA && r.touchShoreB){
				path = new Path(r);
				break;
			}
			if(r.touchShoreA){
				path = findPath(r, rockList);
				if(path != null){
					break;
				}
			}
		}
		if(path != null ){
			System.out.println(path);
		}
	}
	public static Path findPath(Rock rock, List<Rock> rockList){
		if(rock.neighbers != null){
			return null;
		}
		for(Rock r: rockList){
			if(rock.index != r.index
			&& rock.r + r.r - Math.sqrt(Math.pow(rock.y - r.y, 2) + Math.pow(rock.x - r.x, 2))>0 ){
				if(r.touchShoreB){
					//found path
					Path p = new Path(rock);
					p.next = new Path(r);
					return p;
				}
				List<Rock> neighbers = rock.neighbers;
				if(neighbers == null){
					neighbers = new ArrayList<Rock>();
				}
				neighbers.add(r);
				rock.neighbers = neighbers;
			}
		}
		for(Rock r: rock.neighbers){
			Path next = findPath(r, rockList);
			if(next != null){
				Path p = new Path(rock);
				p.next = next;
				return p;
			}
		}
		return null;
	}
}

class Path{
	Rock r;
	Path next;
	Path(Rock r){
		this.r = r;
	}
	@Override
	public String toString(){
		return r.index + (next == null ? "" : ("->" + next.toString()));
	}
}
class Rock{
	int index;
	int x; 
	int y;
	int r; 
	boolean touchShoreA = false; 
	boolean touchShoreB = false; 
	// neighbersClosertoShore, y + r bigger or equals this
	List<Rock> neighbers;
	Rock(int index, int x, int y, int r, int shore_a, int shore_b){
		this.x = x; 
		this.y = y; 
		this.r = r;
		this.index = index;
		this.touchShoreA = (Math.abs(y - r) <= r) ;
		this.touchShoreB = (Math.abs(shore_b - y)<= r); 
	}
}

Cutting to the cheese - dropping all useless information the problem is succinctly summarised by :
=======================================
Given a list of circles of various radii and centre:
1. Would it be possible to move from one starting point to another
2. What would be the min path and the circles
=======================================
Thus we end up having a directed graph, where :
======
1. Nodes are the circles
2. Edges between nodes exist, if and only if the circles overlap
3. Circles having centre with y larger than the North bank y are north bank stones
4. Circles having centre with y smaller than the South bank y are south bank stones
=========
Now, we need to find out all paths from one bank to another, and the minimum path.
This is doable by iterating over all source nodes - and rejecting paths.

I'm removing those rocks that are completely contained in bigger rocks and with remaining rocks creating a directed graph and using BFS to find the shortest route

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
 * 
 * @author Nalin.Sharma
 *
 */
/*
 * 
 * BFS implementation
 */
public class RockClimb {
	static class Node{
		
		public Node(int x, int y, int r, int n) {
			super();
			this.x = x;
			this.y = y;
			this.r = r;
			num = n;
		}
		int x;
		int y;
		int r; //radius
		int num;
		Node parent;
	}
	
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = Integer.parseInt(sc.nextLine());
	List<Node> list = new ArrayList<>();
	for (int i = 0; i < n; i++) {
		String [] arr = sc.nextLine().split(" ");
		list.add(new Node(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), i));
	}
	String[] Y = sc.nextLine().split(" ");
	int ylow = Integer.parseInt(Y[1]);
	int yhigh = Integer.parseInt(Y[0]);
	
	boolean [] [] adj = new boolean[n][n];
	boolean [] visited = new boolean[n];
	
	for (int i = 0; i < list.size(); i++) {
		for (int j = i+1; j < list.size(); j++) {
			Node INode = list.get(i);
			Node JNode = list.get(j);
			
			//added
			int ix1 = INode.x - INode.r;
			int ix2 = INode.x + INode.r;
			int iy1 = INode.y - INode.r;
			int iy2 = INode.y + INode.r;
			
			int jx1 = JNode.x - JNode.r;
			int jx2 = JNode.x + JNode.r;
			int jy1 = JNode.y - JNode.r;
			int jy2 = JNode.y + JNode.r;
			
			//clean rocks being completely engulfed by other rocks
			if(jx1 <= ix1 && ix1 <=jx2 && jx1 <= ix2 && ix2 <=jx2 
			&& jy1 <= iy1 && iy1 <=jy2 && jy1 <= iy2 && iy2 <=jy2 ){
				list.remove(i);
				i -= 1;
				continue;
			}
			else if(ix1 <= jx1 && jx1 <=ix2 && ix1 <= jx2 && jx2 <=ix2 
			&& iy1 <= jy1 && jy1 <=iy2 && iy1 <= jy2 && jy2 <=iy2 ){
				list.remove(j);
				j -= 1;
				continue;
			}
			
			
			int x = Math.abs(INode.x - JNode.x);
			int y = Math.abs(INode.y - JNode.y);
			long hypot = x*x + y*y;
			if(hypot <= INode.r + JNode.r){
				//i,j rocks touch each other
				adj [i] [j] = true;
				adj [j] [i] = true;
			}
		}
	}
	Queue<Node> bfs = new LinkedList<>();
	bfs.add(list.get(0));
	Node fNode = null;
	while(!bfs.isEmpty()){
		Node node = bfs.remove();
		if(visited[node.num] == true){
			continue;
		}
		if(node.y + node.r >= yhigh){
			fNode = node;
			break;
		}
		visited[node.num] = true;
		for (int i = 0; i < n; i++) {
			if(adj[node.num][i] == true){
				//line up connected neighbors 
				list.get(i).parent = node;
				bfs.add(list.get(i));
			}
		}
	}
	if(fNode == null){
		System.out.println("-1");
	}
	else{
		int count = 0;
		while(fNode != null){
			fNode = fNode.parent;
			count++;
		}
		System.out.println(count);
	}
	
}
}