// Eduard Liudkevic
// Ik, I gr, komp. model. magistr.

//http://loi.sscc.ru/hpc/statji/efim.htm

import java.*;
import java.util.*;
import java.awt.*;

public class Tr2_Applet extends java.applet.Applet{
	public static int[] randperm(int n,int[] j0){
		Random R=new Random(n+((long)n)<<31);
		int[] j = new int[n];
		int w,k;
		if (j0==null) {
		for (int i=0; i<n; i++)
			j[i]=i;
		}else{
			for (int i=0; i<n; i++)
				j[i]=j0[i];
		}
		for (int i=0; i<n; i++) {
			w=(int)(n*R.nextDouble());
			if (w==n) w=n-1;
			k=j[i]; j[i]=j[w]; j[w]=k;
		}	
		return j;
	}
	
	public static Briauna PirmojiBriauna (Taskas[] Taskai){
		int i,j;
		int mini=0, minj=0;
		long minats = Long.MAX_VALUE;
		
		for (i=0;i<Taskai.length;++i)
			for (j=0;j<Taskai.length;++j)
				if (i!=j)
					if (Taskai[i].Atstumas(Taskai[j])<minats){
						mini = i;
						minj = j;
						minats=Taskai[i].Atstumas(Taskai[j]);
					}
		System.out.println("mini = "+mini+", minj = "+minj);
		return new Briauna(mini,minj,1);
	}
	
	public static int KurTaskas(Taskas a, Taskas b, Taskas c){
		return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
	}


	
	public static int Ieskok3Taska(Taskas[] Taskai, Briauna Br){
		int i,gerastaskas;
		Apskritimas Aps;
		gerastaskas = -1;

		for (i=0;i<Taskai.length;++i)
			if (KurTaskas(Taskai[Br.a],Taskai[Br.b],Taskai[i])<0) break;
		
		if (i<Taskai.length){
			gerastaskas = i;
			Aps = new Apskritimas(Taskai[Br.a],Taskai[Br.b],Taskai[i]);
			for (i=gerastaskas+1;i<Taskai.length;++i){
				if ((KurTaskas(Taskai[Br.a],Taskai[Br.b],Taskai[i])<0)&&(Aps.Viduje(Taskai[i]))){
					gerastaskas = i;
					Aps = new Apskritimas(Taskai[Br.a],Taskai[Br.b],Taskai[i]);
				}
			}
			
		}

		return gerastaskas;
		
	} 
	
	public static boolean ArMiega(Briauna Br, int a, int b){
		boolean m = false ;
		do{
			if (((Br.a==a)&&(Br.b==b))||((Br.a==b)&&(Br.b==a))){
				m = true;
				break;
			}
			Br = Br.sekanti;
		}while (Br != null);
		return m;
	}

	public static Briauna PaskutineBriauna(Briauna Br){
		while (Br.sekanti!=null) Br = Br.sekanti;
		return Br;
	}

/*	public static void Zudyk(Briauna Br, int a, int b){
		do{
			if (((Br.a==a)&&(Br.b==b))||((Br.a==b)&&(Br.b==a))){
				Br.gyvumas = 2;
				break;
			}
			Br = Br.sekanti;
		}while (Br != null);
	}
*/
	public static void Zudyk(Briauna Br, int a, int b){
		do{
			if (((Br.a==a)&&(Br.b==b))||((Br.a==b)&&(Br.b==a))){
				Br.gyvumas = 2;
				Br = Br.sekanti;
				break;
			}
			Br = Br.sekanti;
		}while (Br != null);
	}

	public static Briauna IeskokGyva(Briauna Briaunos){
		boolean maras = true;
		do {
			if (Briaunos.Gyva()) {
				maras = false;
				break;
			}
			Briaunos = Briaunos.sekanti;
		} while (Briaunos != null);
		if (maras) return null; else return Briaunos;
	}

	public static Trianguliacija Triang(Taskas[] Taskai){
		Briauna Briaunos, Br, Brac, Brcb, Brtmp;
		Trianguliacija Trianguliacijos,Tr;
		int c;

		Trianguliacijos = new Trianguliacija(0,0,0);
		Tr = Trianguliacijos;
		Briaunos = PirmojiBriauna(Taskai);
		Br = Briaunos;

		c = Ieskok3Taska(Taskai,Br);
		//System.out.println(c);
		
		if (c == -1){
			Briaunos = new Briauna(Br.b,Br.a,1);
			Br = Briaunos;
		}else{
			Tr.sekanti = new Trianguliacija(Br.a,Br.b,c);
			Tr = Tr.sekanti;
			Br.gyvumas = 2;
			Brac = new Briauna(Br.a,c,1);
			Brcb = new Briauna(c,Br.b,1);
			Br.sekanti = Brac;
			Brac.sekanti = Brcb;
			Br = IeskokGyva(Briaunos);
			//System.out.println(Tr.a+" | "+Tr.b+" | "+Tr.c);
		}

		do{
			c = Ieskok3Taska(Taskai,Br);
			//System.out.println(c);
			Br.gyvumas = 2;
			if (c != -1){
				Brtmp = PaskutineBriauna(Briaunos);
				Tr.sekanti = new Trianguliacija(Br.a,Br.b,c);
				Tr = Tr.sekanti;
				
				if (ArMiega(Briaunos,Br.a,c)){ 
					Zudyk(Briaunos,Br.a,c);
				}else{
					Brtmp.sekanti = new Briauna(Br.a,c,1);
					Brtmp = Brtmp.sekanti;
				}

				if (ArMiega(Briaunos,c,Br.b)){ 
					Zudyk(Briaunos,c,Br.b);
				}else{
					Brtmp.sekanti = new Briauna(c,Br.b,1);
					Brtmp = Brtmp.sekanti;
				}
			}
			Br = IeskokGyva(Briaunos);
			//System.out.println(Tr.a+" | "+Tr.b+" | "+Tr.c);
		}
		while (Br!=null);

		return Trianguliacijos.sekanti;

	}

	public void init() {
		
		
		Integer N =new Integer(20);
		int[] xXx;
		int[] yYy;
		int h,n;		
		String tt;
		Taskas[] Taskai ;
		Trianguliacija Trianguliacijos,Tr;
		Date dd = new Date();
		
		
		//for (N=5;N<1001;++N){
			
			tt = getParameter("tskkiekis");
			if (tt!="") N = N.valueOf(tt);
			n=N.intValue();
			System.out.println("tt= " +tt+"   N= "+N);
			
			xXx = randperm(n+1,null);
			yYy = randperm(n+1,xXx);
			Taskai = new Taskas[n];
			for (h=0; h<n;++h){
				//System.out.println(xXx[h]+"  |  "+yYy[h]+"  |  "+n);
				Taskai[h] = new Taskas(xXx[h],yYy[h]);
			}
			System.out.println("Trianguliacija prie tasku skaiciaus "+n);
			//Taskai[5] = new Taskas(0,10);
			//Taskai[4] = new Taskas(0,0);
			
			System.out.println(dd.toString());
			Trianguliacijos = Triang (Taskai);
			dd = new Date();
			System.out.println(dd.toString());
			
			PTriang = Trianguliacijos;
			Tsk = Taskai;
			//h=0;
			//do{
			//	++h;
			//	//System.out.println(Tr.a+" | "+Tr.b+" | "+Tr.c);
			//	Tr = Tr.sekanti;
			//}while (Tr != null);
			//System.out.println("Trianguliaciju skaicius yra "+h);
		//}
		
		
		//System.out.println(Briaunos.a +"  "+Briaunos.b);
		
	}
	public Trianguliacija PTriang;
	public int kiek;
	public Taskas[] Tsk;
	
	public void paint(Graphics g){
		//appletas naudoja
		int x1,x2,y1,y2;
		int koef = 10;
		int i =0;
		Apskritimas Aps;
		for (i=0;i<Tsk.length;++i){g.fillOval(Tsk[i].x*koef-1,Tsk[i].y*koef-1,2,2);}
		i = 0;
		System.out.println(kiek);
		Trianguliacija TR = PTriang;
		do{
			++i;
			g.setColor(Color.black);
			g.drawLine(Tsk[TR.a].x*koef,Tsk[TR.a].y*koef,Tsk[TR.b].x*koef,Tsk[TR.b].y*koef);
			g.drawLine(Tsk[TR.b].x*koef,Tsk[TR.b].y*koef,Tsk[TR.c].x*koef,Tsk[TR.c].y*koef);
			g.drawLine(Tsk[TR.c].x*koef,Tsk[TR.c].y*koef,Tsk[TR.a].x*koef,Tsk[TR.a].y*koef);
			
			if (i==kiek){
			
				Aps = new Apskritimas(Tsk[TR.a],Tsk[TR.b],Tsk[TR.c]);
			
				x1 = (int)Math.round(Aps.cx*koef)-(int)Math.round(Math.sqrt(Aps.r)*koef);
				y1 = (int)Math.round(Aps.cy*koef)-(int)Math.round(Math.sqrt(Aps.r)*koef);
				x2 = 2*(int)Math.round(Math.sqrt(Aps.r)*koef);
				y2 = 2*(int)Math.round(Math.sqrt(Aps.r)*koef);
				g.setColor(Color.green);
				g.drawOval(x1,y1,x2,y2);
			}
			TR = TR.sekanti;
		}while((TR != null)&&(i<kiek));
	}
	public boolean mouseDown(Event evt, int x, int y) {
		++kiek;
		repaint();
		return true;
	}
	
}// end of main class

class Briauna{
	public int a;
	public int b;
	public int gyvumas; //0 mieganti, 1 gyva, 2 mirusi
	public Briauna sekanti;
	public Briauna(int a, int b){
		this.a = a;
		this.b = b;
		gyvumas = 0;
		sekanti = null;
	}
	public Briauna(int a, int b, int gyv){
		this.a = a;
		this.b = b;
		this.gyvumas = gyv;
		sekanti = null;
	}
	public boolean Gyva(){
		if (gyvumas == 1) return true; else return false;
	}
}

class Taskas{
	public int x;
	public int y;
	public Taskas(int x, int y){
		this.x = x;
		this.y = y;
	}
	public boolean Lygus(Taskas T){
		if ((T.x==this.x)&&(T.y==this.y)) return true; 
			else return false;
	}
	public int Atstumas (Taskas T){
		return (x-T.x)*(x-T.x)+(y-T.y)*(y-T.y);
	}
	public double Atstumas (double x, double y){
		return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y);
	} 
}

class Trianguliacija{
	int a;
	int b;
	int c;
	Trianguliacija sekanti;
	public Trianguliacija(int a, int b, int c){
		this.a = a;
		this.b = b;
		this.c = c;
		this.sekanti = null;
	}
}

class Apskritimas{
	public double cx;
	public double cy;
	public double r;

	public Apskritimas(Taskas a, Taskas b, Taskas c){
		double abc;
		
		abc = (double)((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
		if (abc != 0d){
			double a0, b0, c0;
			double num;
			
			a0 = (double)(a.x * a.x + a.y * a.y);
			b0 = (double)(b.x * b.x + b.y * b.y);
			c0 = (double)(c.x * c.x + c.y * c.y);
			num = a0*(double)(b.y - c.y) + b0*(double)(c.y - a.y) + c0*(double)(a.y - b.y);
			this.cx = num / (2.0d * abc);
			num = a0*(double)(c.x - b.x) + b0*(double)(a.x - c.x) + c0*(double)(b.x - a.x);
			this.cy = num / (2.0d * abc);
			this.r = a.Atstumas(cx,cy);
		
	    }else{
			this.cx = 0;
			this.cy = 0;
			this.r = -1d;
		}
	}
	public boolean Viduje(Taskas T){
		if (T.Atstumas(cx,cy)<r) return true; else return false;
	}
}