컨벡스 헐 (Convex hull)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;
 
 
class Edge {
    int x;
    int y;
     
    Edge (int x, int y){
        this.x = x;
        this.y = y;
    }
}
 
public class ConvexHull {
     
    /*
     * 볼록 껍질
     * https://www.acmicpc.net/problem/1708
     */
     



   static int MINY;
    static int MINX;
 
    public static void main(String[] args) throws IOException {
         
 
        /*
         * 1. Convex hull 생성
         * 1) 최하단, 좌측점을 기준
         * 2) 점을 각도순으로 정렬
         * 3) CCW사용
         * 3.2) 양수 > 0 : STACK에 다음점을 넣고 PASS
         * 3.3) 음수 < 0 : STACK의 마지막 원소 제거, repeat
         */
         
        //System.setIn(new FileInputStream("res/seminar/sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        int T = Integer.parseInt(br.readLine());
        for (int Ti = 1; Ti <= T; Ti++){
 
            int N = Integer.parseInt(br.readLine());
             
            ArrayList A = new ArrayList();
             
            StringTokenizer ST;
            MINY = Integer.MAX_VALUE;
            MINX = Integer.MAX_VALUE;
            for (int i = 1; i <= N; i++){
                ST = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(ST.nextToken());
                int y = Integer.parseInt(ST.nextToken());
                 
                // 1) 최하단, 좌측점을 기준
                if (y < MINY){
                    MINY = y;
                    MINX = x;
                      
                } else if (y == MINY){
                    if (x < MINX){
                        MINY = y;
                        MINX = x;
                    }
                }
                A.add(new Edge(x, y));
            }
             
            // 2) 점을 각도순으로 정렬
             
                Collections.sort(A, new Comparator() {
 
                    @Override
                    public int compare(Edge arg0, Edge arg1) {
                        int ret = ccw(MINX, MINY, arg0.x, arg0.y, arg1.x, arg1.y);
                         
                        if (ret == 1){
                            return -1;
                        } else if (ret == -1){
                            return 1;
                        } else if (ret == 0) {
                            long a = dist(MINX, MINY, arg0.x, arg0.y);
                            long b = dist(MINX, MINY, arg1.x, arg1.y);
                             
                            if (a < b){
                                return -1;
                            } else if (a > b) {
                                return 1;
                            } else if  (a == b) {
                                return 0;
                            }
                        }
                        return 0;
                         
                    }
                });
     
             
            /*
             * 4) STACK과 CCW사용
             * 4.1 CCW(STACK의 마지막 두점, 다음점)
             * 4.2 양수 > 0 : STACK에 다음점을 넣고 PASS
             * 4.3 음수 < 0 : STACK의 마지막 원소 제거, repeat
             */
             
            A.add(new Edge(MINX, MINY));
            Edge XY2 = null
            Edge XY1 = null
            Edge NEXT = null;
            Stack CVH = new Stack();
             
            //0번점, 1번점 stack에 push
            CVH.push(A.get(0));
            CVH.push(A.get(1));
             
             
            for (int i = 2; i < N; i++) {
                while (CVH.size() >= 2){
                    NEXT = A.get(i);
                    XY2 = CVH.pop();
                    XY1 = CVH.peek();               
                     
                    if (ccw(XY1.x, XY1.y, XY2.x, XY2.y, NEXT.x, NEXT.y) > 0){
                        CVH.push(XY2);
                        break;
                    } 
                }
                CVH.push(NEXT);
            }
            bw.write("#"+Ti+" "+CVH.size()+"\n");
             
        }
         
        br.close();
        bw.flush();
        bw.close();
    }
     
    static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        long ret = (x1 * y2 + x2 * y3 + x3 * y1) - (x3 * y2 + x2 * y1 + x1 * y3);
 
        if (ret > 0)
            return 1;
        else if (ret == 0)
            return 0;
        else
            return -1;
    }
 
    static long dist(long x1, long y1, long x2, long y2) {
        return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
    }
 
}