Main.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
 
package fence;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
 
/**
 *
 * @author cteam028
 */
public class Main {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.init();
    }
 
    public void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            int N = Integer.valueOf(line);
 
            Point[] pole = new Main.Point[N];
 
            double tx = 0;
            double ty = 0;
 
            for (int i = 0; i < N; i++) {
                line = br.readLine();
                String a[] = line.split(" ");
 
                pole[i] = new Point();
                Point p = pole[i];
 
                p.x = Integer.valueOf(a[0]);
                p.y = Integer.valueOf(a[1]);
 
                tx += p.x;
                ty += p.y;
            }
 
            tx /= N;
            ty /= N;
 
            for (int i = 0; i < N; i++) {                
                Point p = pole[i];
 
                p.angle = Math.atan2(p.y-ty, p.x-tx);
                p.lensq = (tx - p.x)*(tx - p.x) + (ty - p.y)*(ty - p.y);
            }
 
            Arrays.sort(pole);
 
 
            double maxlen = 0;
            int maxidx = 0;
            for (int i = 0; i < N; i++) {                
                Point p = pole[i];
 
                if(p.lensq > maxlen) {
                    maxlen = p.lensq;
                    maxidx = i;
                }
            }
 
            pole[maxidx].out = true;
            ArrayList<Point> array = new ArrayList<Main.Point>();
            array.add(pole[maxidx]);
 
            for (int i = 1; i < N; i++) {                
                Point left = pole[(maxidx + i - 1) % N];
                Point p = pole[(maxidx + i) % N];
                Point right = pole[(maxidx + i + 1) % N];
 
                int dx = right.x - left.x;
                int dy = right.y - left.y;
 
                int nx = dy;
                int ny = -dx;
 
                if((((tx - left.x)*nx + (ty - left.y)*ny) > 0 ) != (((p.x - left.x)*nx + (p.y - left.y)*ny) > 0)
                        || (Math.abs((tx - left.x)*nx + (ty - left.y)*ny) < Math.abs((p.x - left.x)*nx + (p.y - left.y)*ny) )
                        ){
                    p.out = true;
                    array.add(p);
                }
            }
 
            double lenght = Double.MAX_VALUE;
 
            Point last = array.get(array.size() - 1);
            for (Main.Point point : array) {
                double dirx = point.x - last.x;
                double diry = point.y - last.y;
                double dirlen = Math.sqrt(dirx * dirx + diry*diry);
                dirx /= dirlen;
                diry /= dirlen;
                //System.out.println("dirx " + dirx);
                //System.out.println("diry " + dirx);
 
                double norx = diry;
                double nory = -dirx;
 
                double maxdir = Double.MIN_VALUE;
                double maxnor = Double.MIN_VALUE;
                double mindir = Double.MAX_VALUE;
                double minnor = Double.MAX_VALUE;
 
                for (Point p : array) {
                    double pn = (p.x - last.x)*norx + (p.y - last.y)*nory;
                    double pd = (p.x - last.x)*dirx + (p.y - last.y)*diry;
                    maxdir = Math.max(maxdir, pd);
                    mindir = Math.min(mindir, pd);
                    maxnor = Math.max(maxnor, pn);
                    minnor = Math.min(minnor, pn);
                }
 
                lenght = Math.min(lenght, (maxdir - mindir)*2 + (maxnor - minnor)*2);
                last = point;
            }
 
            System.out.println(lenght);
        }
    }
 
    public class Point implements Comparable<Point>{
        int x, y;
        double angle;
        double lensq;
        boolean out = false;
 
        public int compareTo(Main.Point arg0) {
            return  (angle < arg0.angle)?-1:1;
        }
 
    }
 
}