// TPoint.java

package convexHull;

public class TPoint {
private int x;
private int y;
public TPoint()
{
	x = 0;
	y = 0;
}
public TPoint(int x, int y) {
	super();
	this.x = x;
	this.y = y;
}

public int getX() {
	return x;
}
public void setX(int x) {
	this.x = x;
}
public int getY() {
	return y;
}
public void setY(int y) {
	this.y = y;
}

}

// Jarvis.java

package convexHull;

import java.util.ArrayList;

public class Jarvis {
	public static int vect(TPoint a1,TPoint a2,TPoint b1,TPoint b2)
	{
		return (a2.getX()-a1.getX())*(b2.getY()-b1.getY())-(b2.getX()-b1.getX())*(a2.getY()-a1.getY());
	}
	public static int dist2(TPoint a1,TPoint a2)
	{
		return (a2.getX()-a1.getX())*(a2.getX()-a1.getX())+(a2.getY()-a1.getY())*(a2.getY()-a1.getY());
	}
	public static void Solve(ArrayList<TPoint> a,ArrayList<TPoint> b)
	{
		int i,j,k,m,n,min;
		n = a.size();
		m = 0;
		try
		{
		for(i = 1;i < n;i++)
			if(a.get(i).getY() < a.get(m).getY())
				m = i;
			else if(a.get(i).getY() == a.get(m).getY() && a.get(i).getX() > a.get(m).getX())
				m = i;
		b.add(a.get(m));
		a.set(m, a.get(0));
		a.set(0, b.get(0));
		k = 0;
		min = 1;
		do
		{
			for(j = 1;j < n;j++)
				if(vect(b.get(k),a.get(min),b.get(k),a.get(j)) < 0 || 
						vect(b.get(k),a.get(min),b.get(k),a.get(j)) == 0 &&
						dist2(b.get(k),a.get(min)) < dist2(b.get(k),a.get(j)))
					min = j;
			k++;
			b.add(a.get(min));
			min = 0;
		}
		while(b.get(k).getX() != b.get(0).getX() || b.get(k).getY() != b.get(0).getY());
		}
		catch(IndexOutOfBoundsException ex)
		{
			
		}
	}
}

// Graham.java

package convexHull;

import java.util.ArrayList;

public class Graham {
	public static int direction(TPoint p0,TPoint p1,TPoint p2)
	{
		return (p1.getX()-p0.getX())*(p2.getY()-p0.getY())-(p2.getX()-p0.getX())*(p1.getY()-p0.getY());
	}
	public static int distSquared(TPoint a,TPoint b)
	{
		return (a.getX() - b.getX())*(a.getX() - b.getX())+(a.getY()-b.getY())*(a.getY()-b.getY());
	}
	public static boolean comp(TPoint p0,TPoint a,TPoint b)
	{
		int d = direction(p0,a,b);
		if(d != 0)
			return d>0;
		else
			return distSquared(p0,a) > distSquared(p0,b); 
	}
	public static void heapify(int l,int r,ArrayList<TPoint> A)
	{
		int i,j;
		TPoint x;
		boolean isCorrect;
		x = A.get(l);
		i = l;
		j = 2 * i;
		isCorrect = false;
		while(j <= r && !isCorrect)
		{
			if(j < r && comp(A.get(0),A.get(j),A.get(j+1)))
				j++;
			if(comp(A.get(0),x,A.get(j)))
			{
				A.set(i, A.get(j));
				i = j;
				j = 2 * i;
			}
			else
				isCorrect = true;
		}
		A.set(i, x);
	}
	public static void buildHeap(ArrayList<TPoint> A)
	{
		int n;
		n = A.size()-1;
		for(int i = n/2;i >= 1;i--)
			heapify(i,n,A);
	}
	public static void heapSort(ArrayList<TPoint> A)
	{
		TPoint x;
		int n = A.size()-1;
		buildHeap(A);
		for(int i = n;i >= 2;i--)
		{
			x = A.get(1);
			A.set(1, A.get(i));
			A.set(i, x);
			heapify(1,i - 1,A);
		}
	}
	public static int removeDup(ArrayList<TPoint> A,ArrayList<TPoint> B)
	{
		int i,prev,count,size;
		size = A.size();
		prev = 1;
		for(i = 1; i < size;i++)
		{
			if(direction(A.get(0),A.get(i),A.get(prev))!=0)
			{
				prev++;
				B.add(A.get(prev));
				A.set(prev, A.get(i));
			}	
		}
		i = prev + 1;
		try
		{
			while(!B.isEmpty())
			{
				System.out.println(i+" "+size);
				A.set(i, B.get(0));
				B.remove(0);
				i++;
			}
			System.out.println();
			}
			catch(IndexOutOfBoundsException ex)
			{
				
			}
		count = prev + 1;
		return count;
	}
	public static void Solve(ArrayList<TPoint> P,ArrayList<TPoint> S)
	{
		int j,m,n,min,top;
		TPoint temp;
		n = P.size();
		min = 0;
		for(int i = 1;i < n;i++)
			if(P.get(i).getY() < P.get(min).getY() || (P.get(i).getY() == P.get(min).getY() && P.get(i).getX() < P.get(min).getX()))
				min = i;
		temp = P.get(0);
		P.set(0, P.get(min));
		P.set(min, temp);
		heapSort(P);
		while(!S.isEmpty())
			S.remove(0);
		m = removeDup(P,S);
		while(!S.isEmpty())
			S.remove(0);
		top = -1;
		try
		{
		top++;
		S.add(top,P.get(0));
		top++;
		S.add(top,P.get(1));
		top++;
		S.add(top,P.get(2));
		for(int i = 3;i < m;i++)
		{
			while(direction(S.get(top-1),S.get(top),P.get(i))<=0)
			{
				S.remove(top);
				top--;
			}
			top++;
			S.add(P.get(i));
		}
		S.add(P.get(0));
		}
		catch(IndexOutOfBoundsException ex)
		{
			
		}
	}
}

// ConvexHull.java

package convexHull;

import java.awt.Canvas;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.ArrayList;

import javax.swing.JFrame;

public class ConvexHull extends Canvas implements MouseListener{
	private static int countA;
	private static int countB;
	private static ArrayList<TPoint> A = new ArrayList<TPoint>();
	private static ArrayList<TPoint> B = new ArrayList<TPoint>();
	private static Graphics gDC;
	public ConvexHull() {
		// TODO Auto-generated constructor stub
		countA = 0;
		countB = 0;
		addMouseListener((MouseListener) this);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		JFrame jf = new JFrame("Convex Hull");
		ConvexHull convexHull = new ConvexHull();
		jf.setSize(800, 600);
		jf.setVisible(true);
		jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		jf.add(convexHull);
	}

	public void paint(Graphics gDC)
	{
		for(int i = 0;i < countA;i++)
			gDC.fillOval(A.get(i).getX()-5, A.get(i).getY()-5, 10, 10);
		for(int i = 0;i < countB;i++)
		{
			gDC.drawLine(B.get(i).getX(),B.get(i).getY(), B.get((i+1)%countB).getX(),B.get((i+1)%countB).getY());
			System.out.println(B.get(i).getX() + " "+ B.get(i).getY());
		}
		System.out.println();	
	}
	
	@Override
	public void mouseClicked(MouseEvent e) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public void mouseEntered(MouseEvent e) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public void mouseExited(MouseEvent e) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public void mousePressed(MouseEvent e) {
		// TODO Auto-generated method stub
		int x = e.getX();
		int y = e.getY();
		TPoint point = new TPoint(x,y);
		A.add(point);
		countA++;
		while(!B.isEmpty())
			B.remove(B.get(0));
		//Jarvis.Solve(A, B);
		Graham.Solve(A, B);
		countB = B.size();
		repaint();
	}

	@Override
	public void mouseReleased(MouseEvent e) {
		// TODO Auto-generated method stub
		
	}

}