Advertisement
Guest User

Untitled

a guest
Feb 6th, 2014
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.22 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main
  5. {
  6.  
  7.     Pii m = new Pii(0, 0);
  8.  
  9.     class Pii implements Comparable<Pii>
  10.     {
  11.  
  12.     int x, y;
  13.  
  14.     Pii(int x, int y)
  15.     {
  16.         this.x = x;
  17.         this.y = y;
  18.     }
  19.    
  20.     @Override
  21.     public int compareTo(Pii a)
  22.     {
  23.         if (Main.sr(m, this, a))
  24.         {
  25.         return -1;
  26.         }
  27.         return 1;
  28.     }
  29.     }
  30.    
  31.     static double dist(Pii a, Pii b)
  32.     {
  33.     return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  34.     }
  35.    
  36.     static boolean sr(Pii m, Pii a, Pii b)
  37.     {
  38.     int t = (m.x + a.x) * (m.y - a.y) + (a.x + b.x) * (a.y - b.y) + (b.x + m.x) * (b.y - m.y);
  39.     if (t != 0)
  40.     {
  41.         return t > 0;
  42.     }
  43.     else
  44.     {
  45.         return dist(m, a) > dist(m, b);
  46.     }
  47.     }
  48.    
  49.     Pii[] a;
  50.    
  51.     BufferedReader input = new BufferedReader(
  52.         new InputStreamReader(System.in));
  53.     public StringTokenizer stoken = new StringTokenizer("");
  54.  
  55.    
  56.     private String nextString() throws IOException {
  57.         while (!stoken.hasMoreTokens()){
  58.             String st = input.readLine();
  59.             stoken = new StringTokenizer(st);
  60.         }
  61.     return stoken.nextToken();
  62.     }
  63.    
  64.     private int nextInt() throws IOException
  65.     {
  66.     return Integer.parseInt(nextString());
  67.     }
  68.    
  69.     public void main() throws IOException
  70.     {
  71.     int n = nextInt();
  72.     a = new Pii[n];
  73.     int x, y;
  74.     for (int i = 0; i < n; i++)
  75.     {
  76.         x = nextInt();
  77.         y = nextInt();
  78.         a[i] = new Pii(x, y);
  79.     }
  80.     m = a[0];
  81.     for (int i = 0; i < n; i++)
  82.     {
  83.         if (m.x > a[i].x)
  84.         {
  85.         m = a[i];
  86.         }
  87.         else if (m.x == a[i].x)
  88.         {
  89.         if (m.y > a[i].y)
  90.         {
  91.             m = a[i];
  92.         }
  93.         }
  94.     }
  95.     Arrays.sort(a);
  96.     Pii []v = new Pii[n];
  97.     int vs = 0;
  98.     for (int i = 0; i < n; i++)
  99.     {
  100.         if (vs < 2)
  101.         {
  102.         v[vs]=(a[i]);
  103.         vs++;
  104.         }
  105.         else
  106.         {
  107.         if (!sr(v[vs - 2], v[vs - 1], a[i]))
  108.         {
  109.             vs--;
  110.             i--;
  111.         }
  112.         else
  113.         {
  114.             v[vs] = (a[i]);
  115.             vs++;
  116.         }
  117.         }
  118.     }
  119.     double res = 0;
  120.     for (int i = 0; i < vs - 1; i++)
  121.     {
  122.         res += dist(v[i], v[i + 1]);
  123.     }
  124.     res += dist(v[0], v[vs - 1]);
  125.     System.out.print(res);
  126.     }
  127.    
  128.     public static void main(String[] args) throws IOException
  129.     {
  130.     Main m = new Main();
  131.     m.main();
  132.     }
  133.    
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement