Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Graham Scan

· ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```// graham scan incomplete

```
import java.io.BufferedWriter;
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
*/

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:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.