Cod sursa(job #3269426)

Utilizator lucky1992Ion Ion lucky1992 Data 19 ianuarie 2025 01:38:30
Problema Infasuratoare convexa Scor 10
Compilator java Status done
Runda Arhiva educationala Marime 3.63 kb
import java.io.*;
import java.util.*;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  public static class Point implements Comparable<Point> {
    public double x;
    public double y;

    public Point(double x, double y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public int compareTo(Point o) {
      if (Double.compare(this.y, o.y) < 0) return -1;
      if (Double.compare(this.y, o.y) > 0) return 1;
      return Double.compare(this.x, o.x);
    }

    @Override
    public String toString() {
      return Double.toString(x) + " " +Double.toString(y);
    }
  }

  public static int ccw(Point p, Point a, Point b) {
    double sign = (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x);
    // clockwise
    // collinear
    return Double.compare(sign, 0.0d); // counter-clockwise
  }

  public static class PolarOrderComparator implements Comparator<Point> {

    private Point p;

    public PolarOrderComparator(Point p) {
      this.p = p;
    }

    @Override
    public int compare(Point p1, Point p2) {
      double dy1 = p1.y - p.y;
      double dy2 = p2.y - p.y;
      double dx1 = p1.x - p.x;
      double dx2 = p2.x - p.x;

      if (dy1 >= 0 && dy2 < 0) return -1; // p1 above & p2 below
      else if (dy1 < 0 && dy2 >= 0) return 1; // p1 below & p2 above
      else if (dy1 == 0.0d && dy2 == 0.0d) {
        if (dx1 >= 0 && dx2 < 0) return -1;
        else if (dx1 < 0 && dx2 >= 0) return 1;
        else return 0;
      }

      return -ccw(p, p1, p2);
    }
  }

  public static void main(String[] args) throws IOException {
    try(MyScanner scanner = new MyScanner("infasuratoare.in");
        PrintWriter pw = new PrintWriter(new FileOutputStream("infasuratoare.out"))) {
      int N = scanner.nextInt();

      Point[] points = new Point[N+1];

      for (int i = 1; i <= N; i++) {
        points[i] = new Point(scanner.nextDouble(), scanner.nextDouble());
      }

      Point p = points[1];

      for (int i = 2; i <= N; i++) {
        if (points[i].compareTo(p) < 0) {
          p = points[i];
        }
      }

      Arrays.sort(points, 1, N+1, new PolarOrderComparator(p));

      Deque<Point> stack = new LinkedList<>();
      stack.push(points[1]);
      stack.push(points[2]);

      for (int i = 3; i <= N; i++) {
        Point top = stack.pop();
        while (!stack.isEmpty() && ccw(stack.peek(), top, points[i]) <= 0) {
          top = stack.pop(); // go to next one
        }
        //re-insert last pop because it was ok actually
        stack.push(top);
        stack.push(points[i]);
      }

      int convexHullSize = stack.size();
      pw.println(convexHullSize);
      for (int i = 0; i < convexHullSize; i++) {
        pw.println(stack.removeLast());
      }
    }
  }
}