Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main
- {
- Pii m = new Pii(0, 0);
- class Pii implements Comparable<Pii>
- {
- int x, y;
- Pii(int x, int y)
- {
- this.x = x;
- this.y = y;
- }
- @Override
- public int compareTo(Pii a)
- {
- if (Main.sr(m, this, a))
- {
- return -1;
- }
- return 1;
- }
- }
- static double dist(Pii a, Pii b)
- {
- return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- static boolean sr(Pii m, Pii a, Pii b)
- {
- 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);
- if (t != 0)
- {
- return t > 0;
- }
- else
- {
- return dist(m, a) > dist(m, b);
- }
- }
- Pii[] a;
- BufferedReader input = new BufferedReader(
- new InputStreamReader(System.in));
- public StringTokenizer stoken = new StringTokenizer("");
- private String nextString() throws IOException {
- while (!stoken.hasMoreTokens()){
- String st = input.readLine();
- stoken = new StringTokenizer(st);
- }
- return stoken.nextToken();
- }
- private int nextInt() throws IOException
- {
- return Integer.parseInt(nextString());
- }
- public void main() throws IOException
- {
- int n = nextInt();
- a = new Pii[n];
- int x, y;
- for (int i = 0; i < n; i++)
- {
- x = nextInt();
- y = nextInt();
- a[i] = new Pii(x, y);
- }
- m = a[0];
- for (int i = 0; i < n; i++)
- {
- if (m.x > a[i].x)
- {
- m = a[i];
- }
- else if (m.x == a[i].x)
- {
- if (m.y > a[i].y)
- {
- m = a[i];
- }
- }
- }
- Arrays.sort(a);
- Pii []v = new Pii[n];
- int vs = 0;
- for (int i = 0; i < n; i++)
- {
- if (vs < 2)
- {
- v[vs]=(a[i]);
- vs++;
- }
- else
- {
- if (!sr(v[vs - 2], v[vs - 1], a[i]))
- {
- vs--;
- i--;
- }
- else
- {
- v[vs] = (a[i]);
- vs++;
- }
- }
- }
- double res = 0;
- for (int i = 0; i < vs - 1; i++)
- {
- res += dist(v[i], v[i + 1]);
- }
- res += dist(v[0], v[vs - 1]);
- System.out.print(res);
- }
- public static void main(String[] args) throws IOException
- {
- Main m = new Main();
- m.main();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement