Over a million developers have joined DZone.

Graham Scan

·
// graham scan incomplete


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Stack;
/*
ID: kanishk1
LANG: JAVA
TASK: moat
*/

public class moat {
	static class Point implements Comparable {
		public int x; public int y;
		Point pv;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public void setPivot(Point pv) {
			this.pv = pv;
		}
		public int compareTo(Object o) {
			Point p = (Point)o;
			double a1 = ((y-pv.y)*1.0)/(x-pv.x);
			if(a1<0) a1 = 2+a1;
			double a2 = ((p.y-pv.y)*1.0)/(p.x-pv.x);
			if(a2<0) a2 = 2+a2;
			if(a1>a2) return 1;
			else if(a1 0) {
		        	stack.push(points[i]);
		        }
		        else {
		                while (o <= 0 && stack.size() > 2) {
		                        stack.pop();
		                        top = (Point)stack.pop();
		        		    	second = (Point)stack.pop();
		                        o = Cross_product(second, top, points[i]);
		                        stack.push(second);
		        		        stack.push(top);
		                }
		                stack.push(points[i]);
		        }
		    }
		    System.out.println("Done");
			while(stack.size()>0) {
				Point pp = (Point)stack.pop();
				System.out.println(pp.x+" "+pp.y);
			}
		    //out.println(ans);                        
		    out.close();                                 
		    System.exit(0); 
	 }
	 
	 private static int Cross_product(Point p1, Point p2, Point p3) {
		 return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);	
	 }
}

Topics:

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}