참고로 Apache Hama를 가지고 distributed convex optimization 구현도 찾아볼 수 있다 :)
http://www.slideshare.net/rogerz1234567/distributed-convex-optimization-thesis-behroz-sikander
import java.util.Scanner; public class Main { private static Stack hull; private static Point first; public static void solve(Point[] pts) { int N = pts.length; Point[] points = new Point[N]; for (int i = 0; i < N; i++) points[i] = pts[i]; Point[] tmp = new Point[points.length]; mergeSort(0, points.length - 1, points, tmp, false); first = points[0]; mergeSort(1, points.length - 1, points, tmp, true); hull.push(points[0]); hull.push(points[1]); for(int i = 2; i < N; i++) { Point head = points[i]; Point middle = hull.pop(); Point tail = hull.peek(); int turn = ccw(tail, middle, head); switch(turn) { case 1: hull.push(middle); hull.push(head); break; case -1: i--; break; case 0: hull.push(head); break; } } } public static void mergeSort(int low, int high, Point[] a, Point[] tmp, boolean isFirst) { if (low < high) { int mid = low + (high - low) / 2; mergeSort(low, mid, a, tmp, isFirst); mergeSort(mid + 1, high, a, tmp, isFirst); merge(low, mid, high, a, tmp, isFirst); } } private static void merge(int low, int mid, int high, Point[] a, Point[] tmp, boolean isFirst) { for (int i = low; i <= high; ++i) { tmp[i] = a[i]; } int i = low; int j = mid + 1; int k = low; while (i <= mid && j <= high) { boolean comp; if (isFirst) { comp = tmp[i].compareTo2(tmp[j]) <= 0; } else { comp = tmp[i].compareTo(tmp[j]) <= 0; } if (comp) { a[k] = tmp[i]; i++; } else { a[k] = tmp[j]; j++; } k++; } while (i <= mid) { a[k] = tmp[i]; k++; i++; } } static Point[] stack = new Point[1000000]; public static class Stack { private int top; int size; public Stack(int size) { this.size = size; top = -1; } public void push(Point v) { if (top == size - 1) { System.out.println("stack is full"); } else { size++; top++; stack[top] = v; } } public Point pop() { if (!isEmpty()) { size--; return stack[top--]; } else { return null; } } public Point peek() { if (isEmpty()) return null; return stack[top]; } public boolean isEmpty() { return top == -1; } public int size() { return top + 1; } public Point[] getArray() { Point[] tmp = new Point[this.size()]; for (int i = 0; i < this.size(); i++) { tmp[i] = stack[i]; } return tmp; } } public static int ccw(Point p1, Point p2, Point p3) { double area2 = (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x); if (area2 < 0) return -1; else if (area2 > 0) return +1; else return 0; } public static class Point implements Comparable{ double x, y; public Point(int x, int y) { this.x = x; this.y = y; } public String toString() { return "(" + x + ", " + y + ")"; } public int compareTo(Point that) { if (this.y < that.y) return -1; if (this.y > that.y) return +1; if (this.x < that.x) return -1; if (this.x > that.x) return +1; return 0; } public int compareTo2(Point q2) { double dx1 = this.x - first.x; double dy1 = this.y - first.y; double dx2 = q2.x - first.x; double dy2 = q2.y - first.y; if (dy1 >= 0 && dy2 < 0) return -1; else if (dy2 >= 0 && dy1 < 0) return +1; else if (dy1 == 0 && dy2 == 0) { if (dx1 >= 0 && dx2 < 0) return -1; else if (dx2 >= 0 && dx1 < 0) return +1; else return 0; } else { return -ccw(first, this, q2); } } } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Point[] points = new Point[N]; hull = new Stack(N + 1); for (int i = 0; i < N; i++) { int x = sc.nextInt(); int y = sc.nextInt(); points[i] = new Point(x, y); } solve(points); System.out.println(hull.size()); sc.close(); } }
No comments:
Post a Comment