import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;

import java.awt.geom.*;


public class PolyWedgeLong {
    Complex[] z=new Complex[100];
    int count;


    public PolyWedgeLong() {}


    public PolyWedgeLong(int cc,Complex[] zz) {
	this.count=cc;
	for(int i=1;i<=cc;++i) z[i]=new Complex(zz[i]);
    }

    public GeneralPath toGeneralPath() {
	GeneralPath gp=new GeneralPath();
	gp.moveTo((float)(z[1].x),(float)(z[1].y));
	for(int i=1;i<=count;++i) {
	    gp.lineTo((float)(z[i].x),(float)(z[i].y));
	}
	gp.closePath();
	return(gp);
    }


/*this routine finds the lowest point of
  a polygon.  if there are more than one
  of these points, the routine picks the
  last one.*/


    public static int extreme(Complex u,PolyWedgeLong P) {
         double test,min;
         int X;
         min=10000.0;
         X=0;
	 Complex v;
         for(int i=1;i<=P.count;++i) {
	     v=Complex.times(u,P.z[i]);
	     test=v.y;
            if(test<min) {
             X=i;
	     min=test;
	    }
	 }
	 return(X);
    }



    public static PolyWedgeLong cheapHull(PolyWedgeLong P) {
	PolyWedgeLong Q=new PolyWedgeLong();
	int[] n=new int[100];
	Complex u=new Complex();
	for(int i=1;i<=32;++i) {
	    double theta=1.0*Math.PI*i/16.0+Math.PI/32.0;
	    u=new Complex(Math.cos(theta),Math.sin(theta));
	    n[i]=extreme(u,P);
	}
	int ct=1;
	Q.z[1]=P.z[n[1]];
	for(int i=2;i<=32;++i) {
	    if(n[i]!=n[i-1]) {
	       ++ct;
	       Q.z[ct]=P.z[n[i]];
	    }
	}
	Q.count=ct;
	return(Q);
    }



  public static int bottom(PolyWedgeLong P) {
     double test,min;
     int X;
     min=10000.0;
     X=0;
     for(int i=1;i<=P.count;++i) {
       test=P.z[i].y;
       if(test<min) {
          X=i;
	  min=test;;
       }
     }
  return(X);
  }




/*given a polygon with a horizontal edge,
  this routine finds the point immediately
  counterclockwise from the edge*/


    public static int nextPoint(PolyWedgeLong P,int n) {

      double test,min;
      Complex w=new Complex();
      int X;
      min=100.0;
      X=0;
      for(int i=1;i<=P.count;++i) {
         if(i!=n) {
           w=Complex.minus(P.z[i],P.z[n]);
           w=Complex.unit(w);
           test=Complex.dist(w,new Complex(1.0,0.0));
           if(min>test) {
             min=test;
             X=i;
	   }
	 }
      }
  return(X);
}



/*this routine rotates a polygon so that
  the edge determined by the indices a and b
  is horizontal*/


 public static PolyWedgeLong roll(PolyWedgeLong P,int a,int b) {
   int i;
   Complex w=new Complex();
   PolyWedgeLong Q=new PolyWedgeLong();

   w=Complex.minus(P.z[b],P.z[a]);
   w=Complex.unit(w);
   for(i=1;i<=P.count;++i) {
     Q.z[i]=Complex.divide(P.z[i],w);
   }
   Q.count=P.count;
   return(Q);
}





    public static PolyWedgeLong convexHull(PolyWedgeLong P) {

	PolyWedgeLong Q=new PolyWedgeLong();
	int[] n=new int[100];
        int match;
        int ct;
	for(int i=1;i<=P.count;++i) Q.z[i]=new Complex(P.z[i]);
	Q.count=P.count;
        n[1]=bottom(Q);
        match=0;
        ct=1;

        while(match==0) {
           n[ct+1]=nextPoint(Q,n[ct]);
           if(n[ct+1]==n[1]) match=1;
           if(ct>P.count) match=1;
           if(n[ct+1]==0) match=1;
           Q=roll(Q,n[ct],n[ct+1]); 
           ++ct;
	}
	for(int i=1;i<=ct;++i) 	Q.z[i]=P.z[n[i]];
	Q.count=ct;
	return(Q);

    }



}