同问,我用的是Melkman,为什么不排序就通不过呢?


//*****************
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s =new Scanner(System.in);
        int N =s.nextInt(), L =s.nextInt();
        Point[] pg =new Point[N];
        for(int i=0;i<N;i++){
            int x =s.nextInt();
            int y =s.nextInt();
            pg[i] =new Point(x,y);
        }
        java.util.Arrays.sort(pg);       //为什么需要排序呢?
        Point[] convex =new Point[N+1];
        int size =getPolygonConvexClosure(pg,0,N,convex,0);
        convex[size] =convex[0];
        double dist =0;
        for(int i=0;i<size;i++) dist += Math.sqrt(Point.distanceSq(convex[i],convex[i+1]));
        dist += 2*Math.PI*L;
        System.out.print(Math.round(dist));
    }
    public static int getPolygonConvexClosure(Point[] pg,int fromIndex,int toIndex,Point[] convex,int offset){
        int len =toIndex -fromIndex;
        Point[] tmp =new Point[2*len];
        tmp[len] =pg[fromIndex];
        tmp[len+1] =pg[fromIndex+1];
        tmp[len+2] =pg[fromIndex+2];
        tmp[len-1] =tmp[len+2];
        if(multiply(tmp[len],tmp[len+1],tmp[len+2])<0){
            tmp[len+1] =pg[fromIndex];
            tmp[len  ] =pg[fromIndex+1];
        }
        int tail =len-2, head =len+3;
        for(int index=fromIndex+3;index<toIndex;index++){
            tmp[tail] =tmp[head] =pg[index];
            if(multiply(tmp[head-2],tmp[head-1],tmp[head])>=0&&
                 multiply(tmp[tail+2],tmp[tail+1],tmp[tail])<=0) continue;
            while(multiply(tmp[head-2],tmp[head-1],tmp[head])<0){
                tmp[head-1] =tmp[head];
                head --;
            }
            while(multiply(tmp[tail+2],tmp[tail+1],tmp[tail])>0){
                tmp[tail+1] =tmp[tail];
                tail++;
            }
            tail --;
            head ++;
        }
        System.arraycopy(tmp,tail+1,convex,offset,head-tail-2);
        return head -tail -2;
    }
    private static int multiply(Point a,Point b,Point c){
        return multiply(a,b,a,c);
    }
    /**
    * 计算向量ab与cd的叉积
    */
    private static int multiply(Point a,Point b,Point c,Point d){
        return (b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y);
    }
}
class Point implements Comparable<Point>{
    public int x,y;
    public static int distanceSq(Point p1,Point p2){
        return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
    }
    public Point(){
        this(0,0);
    }
    public Point(int x,int y){
        this.x =x;
        this.y =y;
    }
    /**
    * 实现Comparable的compareTo方法,将Point按从左到右,从下到上排序
    */
    public int compareTo(Point p){
        return x ==p.x?y-p.y:x-p.x;
    }
}