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

public class MyPolygon
{
	Point pts[];
	int num_pts;
	DeflationApplet applet;

	/*
	    Initialize a polygon with num points.
	*/

	public MyPolygon(int num, DeflationApplet _d)
	{
		int i;
		Random r = new Random();
		applet = _d;
		if(num == -1){
			num = (int) Math.floor(r.nextDouble() * 10);
			num *= 4;
			num -= (Math.floor(r.nextDouble()) % 4);
		}
		pts = new Point[num];
		num_pts = num;
		for(i = 0; i < num_pts; i++){
			pts[i] = new Point();
		}
			
	}

	public void makeRandomPoly(int width, int height)
	{
		double greatest_x, least_x, least_y;
		int greatest_pt = 0;
		int i;
		Vector v;
		Random r = new Random();

		for(i = 0; i < num_pts; i++){
			pts[i].x = r.nextDouble() * width;
			pts[i].y = r.nextDouble() * height;
		}
		greatest_x = pts[0].x;
		least_x = pts[0].x;
		least_y = pts[0].y;
		for(i = 0; i < num_pts; i++){
			if(pts[i].x < least_x){
				least_x = pts[i].x;
				least_y = pts[i].y;
			}
			if(pts[i].x > greatest_x){
				greatest_x = pts[i].x;
				greatest_pt = i;
			}
		}
		pts[greatest_pt].y = least_y;
		Point.splitting_y = least_y;
		Point.sort(pts, new PointComparer());
	}


	/*  
	    This algorithm seems to work. All it really does is compute
	    the point on the line from p1 to p2 that is closest to p[i].
	    Then we find the difference between p[i] and that point.  We
	    then add this difference to the previously computed point,
	    giving this value to p[i].
	*/

	public void reflect2Points(int p1, int p2, boolean poly_is_random)
	{
		double r_sq;
		double x1, x2, x3, y1, y2, y3;
		int i;
		double len1, len2;

		if(!poly_is_random){
			if(!cutIsValid(p1, p2)){
				return;
			}
		} else {
			if(!cutIsValidRandom(p1, p2)){
				return;
			}
		}
		// This is a little hack to make the shorter segments be
		// reflected
		
		i = p1;
		len1 = 0.0;
		while(i != p2){
			len1 += edgeLength(i, (i + 1) % num_pts);
			i++;
			i %= num_pts;
		}
		i = p1;
		len2 = 0.0;
		while(i != p2){
			if(i != 0)
				len2 += edgeLength(i, (i - 1) % num_pts);
			else
				len2 += edgeLength(i, num_pts - 1);
			i--;
			if(i < 0) i = num_pts - 1;
		}
		// if len1 is greater, then switch the cut
		if(len1 > len2){
			int temp = p1;
			p1 = p2;
			p2 = temp;
		}

		// the length of the line segment squared
		r_sq = (pts[p2].x - pts[p1].x) * (pts[p2].x - pts[p1].x) + (pts[p2].y - pts[p1].y) * (pts[p2].y - pts[p1].y);
		x1 = pts[p1].x;
		x2 = pts[p2].x;
		y1 = pts[p1].y;
		y2 = pts[p2].y;

		i = p1 + 1;
		i %= num_pts;

		while(i != p2){
			double x, y, xdiff, ydiff, realx, realy;
			double u;
			x3 = pts[i].x;
			y3 = pts[i].y;
			u = ((x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)) / r_sq;
			x = x1 + u * (x2 - x1);
			y = y1 + u * (y2 - y1);
			xdiff = x3 - x;
			ydiff = y3 - y;
			realx = x - xdiff;
			realy = y - ydiff;
			pts[i].x = realx;
			pts[i].y = realy;
			i++;
			i %= num_pts;
		}
	}

	public boolean cutIsValidRandom(int p1, int p2)
	{
		int i;
		int regular_poly[];
		int poly_1[];
		int poly_2[];
		int count;

		if(!isSimple())
			return true;

		for(i = 0; i < num_pts; i++){
			if(intersect(p1, p2, i, (i + 1) % num_pts)){
				return false;
			}
		}

		if(p2 < p1){ // the rest of the code depends on p1 < p2
			int temp = p1;
			p1 = p2;
			p2 = temp;
		}

		regular_poly = new int[num_pts];
		for(i = 0; i < num_pts; i++){
			regular_poly[i] = i;
		}
		count = 0;
		i = p1;
		while(i != p2){
			i++;
			i %= num_pts;
			count++;
		}
		poly_1 = new int[count + 1];
		count = 0;
		i = p1;
		while(i != p2){
			poly_1[count] = i;
			i++;
			i %= num_pts;
			count++;
		}
		poly_1[count] = i;

		count = 0;
		i = p1;
		while(i != p2){
			i--;
			i += num_pts;
			i %= num_pts;
			count++;
		}

		poly_2 = new int[count + 1];
		count = 0;
		i = p1;
		while(i != p2){
			poly_2[count] = i;
			i--;
			i += num_pts;
			i %= num_pts;
			count++;
		}
		poly_2[count] = i;

		if(Math.abs(Math.abs(area_poly(regular_poly)) - (Math.abs(area_poly(poly_1)) + Math.abs(area_poly(poly_2)))) > 1e-8){
			applet.showStatus("not a valid cut");
			return false;
		}
		applet.showStatus("valid cut");
		return true;
	}


	// Returns true if the cut is valid.  That is, it is 
	// not a line of support and it does not intersect the
	// polygon
	//
	// This only seems to work for quadrilaterals

	public boolean cutIsValid(int p1, int p2)
	{
		double dir;
		// These variables will be positive or negative
		// depending on whether they are a right turn from the cut
		// or not
		double predir = 0.0; // for points > p1 and < p2
		double postdir = 0.0; // for points > p2 and < p1
		int i;

		if(p2 < p1){ // the rest of the code depends on p1 < p2
			int temp = p1;
			p1 = p2;
			p2 = temp;
		}

		for(i = 0; i < num_pts; i++){
			if((i == p1) || (i == p2))
				continue;
			dir = area(p1, p2, i); 
			if(i > p1 && i < p2){
				if(predir == 0){
					// set the direction if it hasn't been set before
					predir = dir;
					// these catch intersections with the polygon
				} else if(predir < 0){
					if(dir > 0){
						return false;
					}
				} else if(predir > 0) {
					if(dir < 0){
						return false;
					}
				}
			} else if(i > p2 || i < p1) { 
				if(postdir == 0){
					postdir = dir;
				} else if(postdir < 0){
					if(dir > 0){
						return false;
					}
				} else if(postdir > 0){
					if(dir < 0){
						return false;
					}
				}
			}
		}

		// These catch lines of support
		if(postdir < 0 && predir < 0)
			return false;
		if(postdir > 0 && predir > 0)
			return false;

		return true;
	}

	public boolean isSimple()
	{
		// UGH! this is an n^2 algorithm
		// There is the O(n) unprogrammable algorithm 
		// by Chazelle, as well as the O(nlog^*n) one
		// by Siedel which is implementable in "around
		// 700 lines of C++".
		// With a decent sorting algorithm, I could put
		// an O(n log n) algorithm in its place, but for right
		// now, I'll leave it.
		int i, j;
		
		for(i = 0; i < num_pts; i++){
			for(j = 0; j < num_pts; j++){
				if(intersect(i, (i + 1) % num_pts, j, (j + 1) % num_pts)){
					return false;
				}
			}
		}
		return true;
	}

	double area_poly(int p[])
	{
		int i;
		double sum = 0.0;
		for(i = 1; i < p.length - 1; i++){
			sum += area(p[0], p[i], p[i + 1]);
		}
		return sum;
	}

	double area(int p1, int p2, int p3)
	{
		double a;
		a = ((pts[p2].x - pts[p1].x) * (pts[p3].y - pts[p1].y)) - 
			((pts[p3].x - pts[p1].x) * (pts[p2].y - pts[p1].y));
		return a;
	}

	boolean left(int p1, int p2, int p3)
	{
		double a;
		a = area(p1, p2, p3);
		return a > 0;
	}

	boolean collinear(int p1, int p2, int p3)
	{
		double a;
		a = area(p1, p2, p3);
		return (Math.abs(a) < 1e-9);
	}

	boolean intersect(int p1, int p2, int q1, int q2)
	{
		boolean l1, l2, l3, l4;

		if((p1 == q1) || (p2 == q1) || (p1 == q2) || (p2 == q2))
			return false;

		//if(collinear(p1, p2, q1) || collinear(p1, p2, q2) || collinear(q1, q2, p1) || collinear(q1, q2, p2))
		//return false;

		l1 = left(p1, p2, q1);
		l2 = left(p1, p2, q2);
		l3 = left(q1, q2, p1);
		l4 = left(q1, q2, p2);

		return (l1 ^ l2) && (l3 ^ l4);
	}

	int nearPoint(int x, int y)
	{
		int i;
		for(i = 0; i < num_pts; i++){
			if(Math.abs(x - pts[i].X) < 5 && Math.abs(y - pts[i].Y) < 5)
				return i;
		}
		return -1;
	}

	public void scaleToSize(int x, int y)
	{
		int i;
		for(i = 0; i < num_pts; i++){
			pts[i].scaleToSize(x, y);
		}
	}

	public double edgeLength(int p1, int p2)
	{
		double xdiff = pts[p1].x - pts[p2].x;
		double ydiff = pts[p1].y - pts[p2].y;
		return Math.sqrt(xdiff * xdiff + ydiff * ydiff);
	}

	/*
	    Draw the polygon in red.
	*/

	void draw(Graphics g)
	{
		int i;
		int poly_x[] = new int[num_pts];
		int poly_y[] = new int[num_pts];

		g.setColor(Color.red);
		scaleToSize(200, 200);

		for(i = 0; i < num_pts; i++){
			poly_x[i] = pts[i].X;
			poly_y[i] = pts[i].Y;
		}
		g.drawPolygon(poly_x, poly_y, num_pts);
	}
}