/******************/
/*  点集合の凸包  */
/******************/

import java.awt.*;

public class mathtotu extends java.applet.Applet {

	Image screen;
	Graphics g_screen;
	Panel ppoint;

	TextField tx,ty;
	Button go,clear;	

	int i,j,x,y,n,tn,start,next,min_y;
	double pie,sht,min,pres;

	boolean dot[][]=new boolean[64][64];

	int px[]=new int[4096];
	int py[]=new int[4096];

	public void init(){

		resize(288,320);
		setBackground(Color.green); /*アプレットの背景を緑にする*/
		setFont(new Font("TimesRoman",Font.PLAIN,12));

		screen=createImage(257,257); 
		g_screen=screen.getGraphics();

		ppoint=new Panel();

		this.setLayout((LayoutManager)null);
		add(ppoint);

		ppoint.setBounds(8,272,256,48);

		ppoint.setLayout(new FlowLayout(FlowLayout.CENTER,4,4));

		tx=new TextField(4);
		ty=new TextField(4);

		tx.setEditable(false); /*テキスト編集不可*/
		ty.setEditable(false);

		tx.setBackground(Color.white);
		ty.setBackground(Color.white);

		go=new Button("G o");
		clear=new Button("Clear");

		ppoint.add(tx);
		ppoint.add(ty);
		ppoint.add(go);
		ppoint.add(clear);

		setPie();

		screenInit();
		repaint();

	}

	public void screenInit() { /*画面初期化*/

		g_screen.setColor(Color.white);
		g_screen.fillRect(0,0,256,256);

		g_screen.setColor(Color.black);

		for (i=0;i<65;i++) { /*セルを描く*/

			g_screen.drawLine(i*4,0,i*4,256);
			g_screen.drawLine(0,i*4,256,i*4);

		}

		for (i=0;i<64;i++)
			for(j=0;j<64;j++)
				dot[j][i]=false;

		n=0;

	}

	public boolean mouseMove(Event evt,int mx,int my){ /*マウス移動*/

		if (mx<16 ||mx>271 ||my<8 ||my>263)
			return false;

		x=(mx-16)/4; /*イメージ上の座標をグラフの座標に変換*/
		y=63-(my-8)/4;

		tx.setText(String.valueOf(x)); /*カーソルの座標表示*/
		ty.setText(String.valueOf(y));

		return true;

	}

	public boolean mouseDown(Event evt,int mx,int my){ /*マウスクリック*/

		if (mx<16 ||mx>271 ||my<8 ||my>263)
			return false;

		x=(mx-16)/4; /*イメージ上の座標をグラフの座標に変換*/
		y=63-(my-8)/4;

		if (dot[x][y]) { /*すでに点が打たれているなら消す*/

			g_screen.setColor(Color.white);
			g_screen.fillRect(x*4+1,(63-y)*4+1,3,3);

			dot[x][y]=false;
			n--;

		} else { /*点が打たれてなければ点を打つ*/

			g_screen.setColor(Color.blue);
			g_screen.fillRect(x*4+1,(63-y)*4+1,3,3);

			dot[x][y]=true;
			px[n]=x;
			py[n]=y;

			n++;

		}

		repaint();

		return true;

	}

	public boolean action(Event evt,Object What) {

		if (evt.target==go) { /*Go ボタン*/

			if (n<2) /*点が２つ以下ならリターン*/
				return false;

			start=hidarishita(); /*左下の点を最初の点にする*/			
			tn=start;

			g_screen.setColor(Color.red);

			pres=0; /*前の角度を０に設定*/

			do {

				min=2*pie;

				for (i=0;i<n;i++) {

					sht=kakudo(px[i]-px[tn],py[i]-py[tn]);

					if (pres<=sht && i!=tn)
						if (min>sht) { /*最小角*/

							min=sht;
							next=i;

						}

				}

				pres=kakudo(px[next]-px[tn],py[next]-py[tn]);

				g_screen.fillRect(px[next]*4+1,(63-py[next])*4+1,3,3);

				g_screen.drawLine(px[tn]*4+2,(63-py[tn])*4+2,
						px[next]*4+2,(63-py[next])*4+2);

				tn=next;

				repaint();

			} while(tn!=start);// &&py[tn]!=min_y);


		}

		if (evt.target==clear) { /*クリアボタン*/

			screenInit();
			repaint();

		}

		return false;

	}

	public int hidarishita() { /*一番左下の点の番号を探す*/

		int min,xmin,tr;

		min=63;
		xmin=63;
		tr=0;

		for (i=0;i<n;i++) { /*一番下の点のy 座標*/

			if (min>py[i]) {

				min=py[i];
				tr=i;

			}

		}
									
		for (i=0;i<n;i++)
			if (py[i]==min) /*一番下の点の中で最も左にある点*/
				if (xmin<px[i]) {

						xmin=px[i];
						tr=i;

				}

		return tr;

	}
	
	public double kakudo(int x,int y) { /*ベクトルの角度を計算*/

		double c,s,sc,vec;
		int rev,deg;

		if (x==0 && y==0) /*零ベクトルなら計算不可*/
			return -1;

		rev=0;

		if (y<0) { /*θ＞πならθからπをひく*/

			y*=-1;
			x*=-1;
			rev=1;

		}

		vec=Math.sqrt(x*x+y*y)*Math.sqrt(32.0*32.0);/*大きさの積*/

		sc=32*x; /*内積*/

		s=Math.acos(sc/vec); /*角度θを求める*/

		if (rev==1) /*θ＞πだったなら先に減じておいたπを足す*/
			s+=pie;

		return s; /*角度θを返す*/

	}

	public void setPie() { /*マチンの公式でπを求める*/

		int j,k;
		double i,w,wrk,p;

		i=3;
		k=-1;

		pie=0.2;
		wrk=1.0/239.0;

		do { /*アークタンジェントを級数展開*/

			p=0.2;
			w=1.0/239.0;

			p=Math.pow(p,(double)i);
			w=Math.pow(w,(double)i);

			pie+=(p/i)*k;
			wrk+=(w/i)*k;

			i+=2;
			k*=-1;

		} while (i<24);

		pie*=4;
		pie-=wrk;

		pie*=4; /*πの値*/

	}

	public void paint(Graphics g){

		g.drawImage(screen,15,7,this);

	}

	public void update(Graphics g){

		paint(g);

	}

}