Submission #941634

---

Source Code Expand

import java.util.*;
public class Main {
  void run() {
    int n = ni();
    int[] x = new int[n];
    int[] y = new int[n];
    for (int i = 0; i < n; ++i) {
      x[i] = ni();
      y[i] = ni();
    }

    long cnt90 = 0;
    long cntdon = 0;
    for (int i = 0; i < n; ++i) {
      // 点iを基準Bとする。
      ArrayList<Vec> list = new ArrayList<>();
      for (int j = 0; j < n; ++j) {
        if (i == j) continue;
        Vec vec = new Vec(j, x[j] - x[i], y[j] - y[i]);
        Vec vec2 = new Vec(j, x[j] - x[i], y[j] - y[i], 2 * Math.PI);
        list.add(vec);
        list.add(vec2);
      }
      Collections.sort(list, new Comparator<Vec>() {
        @Override
        public int compare(Vec o1, Vec o2) {
          return Double.compare(o1.arc, o2.arc);
        }
      });
      for (int j = 0; j < n - 1; ++j) {
        // 点jを基準Aとする
        Vec atom = list.get(j);
        // <ABCが2/pi以上で最小な点を探す
        int left = 0;
        int right = list.size();
        while (right - left > 1) {
          int mid = (left + right) / 2;
          Vec trg = list.get(mid);
          if (trg.arc - atom.arc - 1e-9 > Math.PI / 2.0) {
            right = mid;
          } else {
            left = mid;
          }
        }
        int idx90 = (left + right) / 2;
        if (Math.abs(Math.PI / 2.0 - (list.get(idx90).arc - atom.arc)) < 1e-9) {
          ++cnt90;
        }
        // <ABCがpi以下で最大な点を探す
        left = 0;
        right = list.size();
        while (right - left > 1) {
          int mid = (left + right) / 2;
          Vec trg = list.get(mid);
          if (trg.arc - atom.arc > Math.PI - 1e-9) {
            right = mid;
          } else {
            left = mid;
          }
        }
        int idx180 = (left + right) / 2;
        cntdon += idx180 - idx90;
      }
    }
    long cntei = (long) n * (n - 1) * (n - 2) / 6;
    cntei -= cnt90 + cntdon;
    System.out.println(cntei + " " + cnt90 + " " + cntdon);
  }

  class Vec {
    int id;
    int x, y;
    double arc;

    Vec(int id, int x, int y, double add) {
      this.id = id;
      this.x = x;
      this.y = y;
      arc = Math.atan2(y, x) + add;
    }

    Vec(int id, int x, int y) {
      this(id, x, y, 0);
    }

    @Override
    public String toString() {
      return "{id = " + id + ", arc = " + (arc * 180.0 / Math.PI) + "}";
    }
  }

  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }
}

Submission Info

Judge Result