Cod sursa(job #3287234)

Utilizator lucky1992Ion Ion lucky1992 Data 16 martie 2025 22:49:24
Problema Triang Scor 100
Compilator java Status done
Runda Arhiva de probleme Marime 3.7 kb
import java.io.*;
import java.util.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {

  public static final double EPS = 0.0001d;

  public static final double SQRT_3 = Math.sqrt(3);

  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 String toString() {
      return "(" + x + " , " + y + ")";
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }

      if (o == null || getClass() != o.getClass()) return false;

      Point other = (Point)o;
      return Math.abs(x - other.x) < EPS && Math.abs(y - other.y) < EPS;
    }

    @Override
    public  int hashCode() {
      return Objects.hash(x, y);
    }


    @Override
    public int compareTo(Point o) {
      if (Math.abs(x - o.x) < EPS && Math.abs(y - o.y) < EPS) return 0;
      else if (x < o.x) return -1;
      else if (x > o.x) return 1;
      else if (y < o.y) return -1;
      else return 1;
    }
  }

  public static boolean binarySearch(Point[] points, int low, int high, Point p) {
    int mid;

    while (low <= high) {
      mid = (low + high) >>> 1;

      if (points[mid].equals(p)) {
        return true;
      } else if (Math.abs(points[mid].x - p.x) < EPS) {
        if (points[mid].y < p.y) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      } else if (points[mid].x < p.x) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
    }

    return false;
  }

  public static void main(String[] args) throws IOException {

    try (MyScanner scanner = new MyScanner("triang.in");
        PrintWriter pw = new PrintWriter(new FileOutputStream("triang.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());
      }

      // give it an order aka. sweep it
      Arrays.sort(points, 1, N+1);

      int sol = 0;

      for (int i = 1; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
          Point mid = new Point((points[i].x + points[j].x) / 2, (points[i].y + points[j].y) / 2);

          Point candidate1 = new Point(mid.x + SQRT_3 * (points[i].y - mid.y), mid.y - SQRT_3 * (points[i].x - mid.x));

          if (binarySearch(points, 1, N, candidate1)) {
            sol++;
          }

          Point candidate2 = new Point(mid.x - SQRT_3 * (points[i].y - mid.y), mid.y + SQRT_3 * (points[i].x - mid.x));

          if (binarySearch(points, 1, N, candidate2)) {
            sol++;
          }
        }
      }

      pw.println(sol / 3);
    }
  }
}