import java.applet.*;
import java.awt.*;
import java.util.Vector;

class IntegerArray
{
	private int[] data;
	private int[] old_data;
	private int no_items;
	private int size_increment;
	
	IntegerArray(int initial_size)
	{
		data = new int[initial_size];
		no_items=0;
		size_increment=initial_size;
	}

	void addElement(int item)
	{
		if (no_items==data.length)
		{
			int i;
			int new_size;
			old_data=new int[no_items];
			for(i=0;i<no_items;i++)
				old_data[i]=data[i];
			new_size=no_items+size_increment;
			data = new int[new_size];
			for(i=0;i<no_items;i++)
				data[i]=old_data[i];
		}
		no_items=no_items+1;
		data[no_items-1]=item;
	}
	void setElement(int i, int item)
	{
		if (i<no_items & i>=0) data[i]=item;
	}
	int indexOf(int item)
	{
		int i=0;
		while (i<no_items && elementAt(i)!=item)
			i++;
		if (i>=no_items)
			return -1;
		else
			return i;
	}
	int elementAt(int index)
	{
		return data[index];
	}
	int lastElement()
	{
		return data[no_items-1];
	}
	int firstElement()
	{
		return data[0];
	}
	int noElements()
	{
		return no_items;
	}
}
class VoronoiVertex
{
	double x;
	double y;
	double square_radius;
	int[] forming_points;
	int[] neigh_vertices;

	VoronoiVertex()
	{
		forming_points = new int[3];
		neigh_vertices = new int[3];
	}

}
class Point
{
	double x;
	double y;
}
class VoronoiDiagram
{
	Vector VoronoiVertices;
	Vector Points;
	
	VoronoiDiagram(double x1, double y1, double x2, double y2)
	{
		VoronoiVertices = new Vector();
		Points = new Vector();
		Point p1 = new Point();
		Point p2 = new Point();
		Point p3 = new Point();
		Point p4 = new Point();
		p1.x=x1;
		p1.y=y1;
		p2.x=x2;
		p2.y=y1;
		p3.x=x2;
		p3.y=y2;
		p4.x=x1;
		p4.y=y2;
		Points.addElement(p1);
		Points.addElement(p2);
		Points.addElement(p3);
		Points.addElement(p4);
		VoronoiVertex v1 = new VoronoiVertex();
		VoronoiVertex v2 = new VoronoiVertex();
		v1.x=(x1+x2)/2;
		v1.y=(y1+y2)/2;
		v1.square_radius=(Math.pow(x2-x1,2)+Math.pow(y2-y1,2))/4;
		int[] fp1={0,1,2};
		v1.forming_points=fp1;
		int[] nv1={-1,-1,1};
		v1.neigh_vertices=nv1;
		v2.x=v1.x;
		v2.y=v1.y;
		v2.square_radius=v1.square_radius;
		int[] fp2={0,2,3};
		v2.forming_points=fp2;
		int[] nv2={0,-1,-1};
		v2.neigh_vertices=nv2;
		VoronoiVertices.addElement(v1);
		VoronoiVertices.addElement(v2);
	}
		
	void AddPoint(Point point)
	{
		IntegerArray vertices_to_delete = new IntegerArray(100);
		Vector new_vertices = new Vector();
		Points.addElement(point);
		int vertex_no = StartingVertex();
		vertices_to_delete = VerticesToDelete(vertex_no);
		new_vertices = NewVertices(vertices_to_delete);
		AddNewVertices(new_vertices,vertices_to_delete);
	}

	private int StartingVertex()
	{
		boolean found_vertex = false;
		double d;
		double sr;

		int vn=VoronoiVertices.size();
		Point p = (Point)Points.lastElement();
		VoronoiVertex v;
		while (!found_vertex)
  		{
			v = (VoronoiVertex)VoronoiVertices.elementAt(vn-1);
			d = Math.pow(v.x-p.x,2) + Math.pow(v.y-p.y,2);
			sr = v.square_radius;
			found_vertex = d<=sr;
			if (!found_vertex) vn=vn-1;
		}
		return vn-1;
	}

	private IntegerArray VerticesToDelete(int vertex_no)
	{
		IntegerArray vd;
		vd = new IntegerArray(100);
		IntegerArray vertices_tested;
		vertices_tested = new IntegerArray(100); 
		vd.addElement(vertex_no);
		vertices_tested.addElement(vertex_no);
		int i;
		Point p = (Point)Points.lastElement();
		VoronoiVertex q;
		double d;
		int nv;
		VoronoiVertex v;
		int n=0;
		while (n<vd.noElements())
		{
			vertex_no=vd.elementAt(n);
			v=(VoronoiVertex)VoronoiVertices.elementAt(vertex_no);
			for (i=0;i<3;i++)
			{
				nv=v.neigh_vertices[i];
				if (nv>=0 && vertices_tested.indexOf(nv)<0)
				{
					q=(VoronoiVertex)VoronoiVertices.elementAt(nv);
					d=Math.pow(p.x-q.x,2)+Math.pow(p.y-q.y,2);
					if (d<=q.square_radius) vd.addElement(nv);
					vertices_tested.addElement(nv);
				}
			}
			n++;
		}
		return vd;
	}
	
	private Vector NewVertices(IntegerArray vd)
	{
		Vector new_vertices = new Vector();
		VoronoiVertex v = new VoronoiVertex();
		VoronoiVertex w;
		int[] fp;
		Point[] p;
		double x1,x2,x3,y1,y2,y3,c1,c2;
		for (int i=0;i<vd.noElements();i++)
		{
			v=(VoronoiVertex)VoronoiVertices.elementAt(vd.elementAt(i));
			for(int j=0;j<3;j++)
			{	
				if (vd.indexOf(v.neigh_vertices[j])<0)
				{
					w=new VoronoiVertex();
					fp = new int[3];
					fp[0]=v.forming_points[j];
					if (j==2)
						fp[1]=v.forming_points[0];
					else
						fp[1]=v.forming_points[j+1];
					fp[2]=Points.size()-1;
					w.forming_points=fp;
					p = new Point[3];
					for(int k=0;k<3;k++)
						p[k]=(Point)Points.elementAt(fp[k]);
					x1=p[0].x;
					x2=p[1].x;
					x3=p[2].x;
					y1=p[0].y;
					y2=p[1].y;
					y3=p[2].y;
					c1=Math.pow(x1,2)-Math.pow(x2,2)+Math.pow(y1,2)-Math.pow(y2,2);
					c2=Math.pow(x2,2)-Math.pow(x3,2)+Math.pow(y2,2)-Math.pow(y3,2);
					w.x=.5*(c1*(y2-y3)-c2*(y1-y2))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
					w.y=.5*(c1*(x2-x3)-c2*(x1-x2))/((y1-y2)*(x2-x3)-(y2-y3)*(x1-x2));
					w.square_radius=Math.pow(x1-w.x,2)+Math.pow(y1-w.y,2);
					new_vertices.addElement(w);
				} //end if
			} // end for
		} // end for
		return new_vertices;
	}
	private void AddNewVertices(Vector new_vertices,IntegerArray vertices_to_delete)
	{
		IntegerArray forming_points_list;
		IntegerArray neigh_vertices_list;
		int[][] neigh_matrix;
		int[] vertex_mapping;
		int vertex_no;
		VoronoiVertex v;
		int[] fp;
		int p1,p2,p3;

		forming_points_list = FormingPointsList(new_vertices);
		neigh_vertices_list = NeighVerticesList(vertices_to_delete);
		int n = forming_points_list.noElements();
		neigh_matrix = new int[n][n];
		vertex_mapping = new int[new_vertices.size()];

		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++) neigh_matrix[i][j]=-1;

		for(int i=0;i<vertices_to_delete.noElements();i++)
		{
			vertex_no=vertices_to_delete.elementAt(i);
			v = new VoronoiVertex();
			v = (VoronoiVertex)new_vertices.elementAt(i);
			VoronoiVertices.setElementAt(v,vertex_no);
			fp=v.forming_points;
			p1=forming_points_list.indexOf(fp[0]);
			p2=forming_points_list.indexOf(fp[1]);
			p3=forming_points_list.indexOf(fp[2]);
			neigh_matrix[p1][p2]=vertex_no;
			neigh_matrix[p2][p3]=vertex_no;
			neigh_matrix[p3][p1]=vertex_no;
			vertex_mapping[i]=vertex_no;
		}
		for(int i=vertices_to_delete.noElements();i<new_vertices.size();i++)
		{
			v = new VoronoiVertex();
			v = (VoronoiVertex)new_vertices.elementAt(i);
			VoronoiVertices.addElement(v);
			vertex_no=VoronoiVertices.size()-1;
			fp=v.forming_points;
			p1=forming_points_list.indexOf(fp[0]);
			p2=forming_points_list.indexOf(fp[1]);
			p3=forming_points_list.indexOf(fp[2]);
			neigh_matrix[p1][p2]=vertex_no;
			neigh_matrix[p2][p3]=vertex_no;
			neigh_matrix[p3][p1]=vertex_no;
			vertex_mapping[i]=vertex_no;
		}
		for(int i=0;i<neigh_vertices_list.noElements();i++)
		{
			vertex_no=neigh_vertices_list.elementAt(i);
			v = new VoronoiVertex();
			v = (VoronoiVertex)VoronoiVertices.elementAt(vertex_no);
			fp=v.forming_points;
			p1=forming_points_list.indexOf(fp[0]);
			p2=forming_points_list.indexOf(fp[1]);
			p3=forming_points_list.indexOf(fp[2]);
			if(p1>=0 && p2>=0) neigh_matrix[p1][p2]=vertex_no;
			if(p2>=0 && p3>=0) neigh_matrix[p2][p3]=vertex_no;
			if(p3>=0 && p1>=0) neigh_matrix[p3][p1]=vertex_no;
		}
		for(int i=0;i<new_vertices.size();i++)
		{
			vertex_no=vertex_mapping[i];
			v = new VoronoiVertex();
			v = (VoronoiVertex)VoronoiVertices.elementAt(vertex_no);
			fp=v.forming_points;
			p1=forming_points_list.indexOf(fp[0]);
			p2=forming_points_list.indexOf(fp[1]);
			p3=forming_points_list.indexOf(fp[2]);
			v.neigh_vertices[0]=neigh_matrix[p2][p1];
			v.neigh_vertices[1]=neigh_matrix[p3][p2];
			v.neigh_vertices[2]=neigh_matrix[p1][p3];
		}
		for(int i=0;i<neigh_vertices_list.noElements();i++)
		{
			vertex_no=neigh_vertices_list.elementAt(i);
			v = new VoronoiVertex();
			v = (VoronoiVertex)VoronoiVertices.elementAt(vertex_no);
			fp=v.forming_points;
			p1=forming_points_list.indexOf(fp[0]);
			p2=forming_points_list.indexOf(fp[1]);
			p3=forming_points_list.indexOf(fp[2]);
			if(p1>=0 && p2>=0 && neigh_matrix[p2][p1]>=0)
				v.neigh_vertices[0]=neigh_matrix[p2][p1];
			if(p2>=0 && p3>=0 && neigh_matrix[p3][p2]>=0)
				v.neigh_vertices[1]=neigh_matrix[p3][p2];
			if(p3>=0 && p1>=0 && neigh_matrix[p1][p3]>=0)
				v.neigh_vertices[2]=neigh_matrix[p1][p3];
		}
	}
	private IntegerArray FormingPointsList(Vector new_vertices)
	{
		VoronoiVertex v;
		IntegerArray fplist = new IntegerArray(100);
		for(int i=0;i<new_vertices.size();i++)
		{
			v = (VoronoiVertex)new_vertices.elementAt(i);
			for(int j=0;j<3;j++)
			{
				if(fplist.indexOf(v.forming_points[j])<0)
					fplist.addElement(v.forming_points[j]);
			}
		}
		return fplist;
	}
	private IntegerArray NeighVerticesList(IntegerArray vd)
	{
		VoronoiVertex v;
		IntegerArray nvlist = new IntegerArray(100);
		int vertex_no;
		int nv;
		for(int i=0;i<vd.noElements();i++)
		{
			vertex_no=vd.elementAt(i);
			v = (VoronoiVertex)VoronoiVertices.elementAt(vertex_no);
			for(int j=0;j<3;j++)
			{
				nv = v.neigh_vertices[j];
				if (nv>=0 && nvlist.indexOf(nv)<0 && vd.indexOf(nv)<0)
					nvlist.addElement(nv);
			}
		}
		return nvlist;
	}

}
public class VoronoiDemo extends Applet
{
	private VoronoiDiagram vd;

	public VoronoiDemo()
	{
	}

	public String getAppletInfo()
	{
		return "Name: VoronoiDemo\r\n" +
		       "Author: James Kirby\r\n" +
		       "Created with Microsoft Visual J++ Version 1.0";
	}


	public void init()
	{
        // If you use a ResourceWizard-generated "control creator" class to
        // arrange controls in your applet, you may want to call its
        // CreateControls() method from within this method. Remove the following
        // call to resize() before adding the call to CreateControls();
        // CreateControls() does its own resizing.
        //----------------------------------------------------------------------
		setBackground(Color.white);
		Dimension dim = size();
		vd = new VoronoiDiagram(0,0,dim.width,dim.height);
	}

	public void destroy()
	{
	}

	public void paint(Graphics g)
	{
		int x0,y0,x1,y1;
		VoronoiVertex v0,v1;
		int pn0,pn1;
		Point p0,p1;
		int[] nv,fp;
		p0=new Point();
		p1=new Point();
		for (int i=0;i<vd.VoronoiVertices.size();i++)
		{
			v0=(VoronoiVertex)vd.VoronoiVertices.elementAt(i);
			nv=v0.neigh_vertices;
			fp=v0.forming_points;
			for(int j=0;j<3;j++)
			{
				g.setColor(Color.blue);
				pn0=fp[j];
				if (j<2)
					pn1=fp[j+1];
				else
					pn1=fp[0];
				p0=(Point)vd.Points.elementAt(pn0);
				p1=(Point)vd.Points.elementAt(pn1);
				if (pn0>3 && pn1>3)
				{
					x0=(int)p0.x;
					y0=(int)p0.y;
					x1=(int)p1.x;
					y1=(int)p1.y;
					g.drawLine(x0,y0,x1,y1);
				}
				g.setColor(Color.red);
				x0=(int)v0.x;
				y0=(int)v0.y;
				if (nv[j]>=0)
				{
					v1=(VoronoiVertex)vd.VoronoiVertices.elementAt(nv[j]);
					x1=(int)v1.x;
					y1=(int)v1.y;
				}
				else
				{
					x1=(int)((p0.x + p1.x)/2);
					y1=(int)((p0.y + p1.y)/2);
				}
				g.drawLine(x0,y0,x1,y1);
			}
		}
	}

	public void start()
	{
	}
	
	public void stop()
	{
	}


	public boolean mouseDown(Event evt, int x, int y)
	{
		Graphics g = getGraphics();
		Point p = new Point();
		Point q;
		p.x = x;
		p.y = y;
		boolean NewPoint=true;
		for(int i=0;i<vd.Points.size();i++)
		{
			q=(Point)vd.Points.elementAt(i);
			if((int)q.x==x && (int)q.y==y) NewPoint=false;
		}
		if(NewPoint) vd.AddPoint(p);
		repaint();
		return true;
	}

	public boolean mouseUp(Event evt, int x, int y)
	{
		return true;
	}

}