package GhostBusters;

import java.util.Collections;
import java.util.LinkedList;

public class FindLine {
	//Ghost g has to be the leftmost point of all points in list1 & list2
	//This is used to solve the sub-problem
	//Find a pair of Ghostbuster and Ghost in O(n log n) time
	//such that the line generated by connecting these two
	//have the same number of Ghostbusters and Ghosts above the line
	//and the same number of Ghostbusters and Ghosts below the line
	//Same approach is applicable to Ghostbusters
	static int determinePair(Ghost g, LinkedList<GhostBuster> list1, LinkedList<Ghost> list2) {
		LinkedList<Pair> list1Pairs = new LinkedList<Pair>();
		LinkedList<Pair> list2Pairs = new LinkedList<Pair>();
		for(int i = 0; i < list1.size(); i++){
			list1Pairs.add(new Pair(i, list1.get(i).x - g.x, list1.get(i).y - g.y));
			list2Pairs.add(new Pair(i, list2.get(i).x - g.x, list2.get(i).y - g.y));
		}
		Collections.sort(list1Pairs);
		Collections.sort(list2Pairs);
		int low = 0;
		int high = list1.size() - 1;
		while(low <= high){
			int mid = (low + high)/2;
			int aboveGhostBusters = 0;
			int lowerGhostBusters = 0;
			int aboveGhosts = 0;
			int lowerGhosts = 0;
			double slope = list1Pairs.get(mid).slope;
			for(int i = 0; i < list1Pairs.size(); i++){
				if(i == mid) continue;
				if(list1Pairs.get(i).slope > slope){
					aboveGhostBusters++;
				}else{
					lowerGhostBusters++;
				}
			}
			for(int i = 0; i < list2Pairs.size(); i++){
				if(list2Pairs.get(i).index == list2.indexOf(g)) continue;
				if(list2Pairs.get(i).slope > slope){
					aboveGhosts++;
				}else{
					lowerGhosts++;
				}
			}
			if(aboveGhosts == aboveGhostBusters &&
					lowerGhosts == lowerGhostBusters){
				return list1Pairs.get(mid).index;
			}else if(aboveGhosts - aboveGhostBusters <  0){
				low = mid + 1;
			}else{
				high = mid - 1;
			}
		}
		return -1;
	}
	static class Pair implements Comparable<Pair>{
		int index;
		double slope;
		public Pair(int index, int xDist, int yDist){
			this.index = index;
			if(xDist == 0) this.slope = Double.MAX_VALUE;
			else this.slope = (((double)yDist)/(double)xDist);
			int coord = yDist + 1;
			int coord2 = xDist + 1;
		}
		@Override
		public int compareTo(Pair o) {
			return Double.compare(slope, o.slope);
		}
	}
	static class GhostBuster extends Coordinates{
		public GhostBuster(int x, int y) {
			super(x, y);
		}
	}
	static class Ghost extends Coordinates{
		public Ghost(int x, int y) {
			super(x, y);
		}

	}
	static class Coordinates implements Comparable<Coordinates>{
		int x;
		int y;
		public Coordinates(int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Coordinates o){
			return x == o.x ? Integer.compare(y, o.y) : Integer.compare(x, o.x);
		}
	}
	public static void main(String[] args){
		Ghost g = new Ghost(1,1);
		Ghost g2 = new Ghost(13,14);
		Ghost g3 = new Ghost(6,8);
		GhostBuster gb1 = new GhostBuster(13, -1);
		GhostBuster gb2 = new GhostBuster(4, 16);
		GhostBuster gb3 = new GhostBuster(12, -1);
		LinkedList<Ghost> list2 = new LinkedList<Ghost>();
		list2.add(g);
		list2.add(g2);
		list2.add(g3);
		LinkedList<GhostBuster> list1 = new LinkedList<GhostBuster>();
		list1.add(gb1);
		list1.add(gb2);
		list1.add(gb3);
		Collections.sort(list1);
		Collections.sort(list2);
		int index = determinePair(g, list1, list2);
		System.out.println(list1.get(index).x + " " + list1.get(index).y);
		System.out.println();
	}
}