読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest 033 D: 三角形の分類

解法

ある一点 I を決め、その点を原点として他の点を仰角でソートする。I と他の一点 J を選んだ時に、角 KIJ が鋭角となるような点 K はしゃくとり法によって求められる。

発想自体はこれに近い気がする↓
kenkoooo.hatenablog.com


点の数が多いため、小数点を使った計算は出来れば避けた方が良さそう。整数幾何ライブラリは mamekin さんからコピペした。

コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <string.h>

using namespace std;
typedef signed long long ll;

class Point {
 public:
  int y, x;
  Point() { y = x = 0; }
  Point(int y0, int x0) {
    y = y0;
    x = x0;
  }
  Point operator+(const Point& p) const { return Point(y + p.y, x + p.x); }
  Point operator-(const Point& p) const { return Point(y - p.y, x - p.x); }
  Point operator*(int a) const { return Point(y * a, x * a); }
  long long length2() const { return y * (long long)y + x * (long long)x; }
  long long dist2(const Point& p) const {
    return (y - p.y) * (long long)(y - p.y) + (x - p.x) * (long long)(x - p.x);
  }
  long long dot(const Point& p) const {
    return y * (long long)p.y + x * (long long)p.x;  // |a|*|b|*cosθ
  }
  long long cross(const Point& p) const {
    return x * (long long)p.y - y * (long long)p.x;  // |a|*|b|*sinθ
  }

  static bool Sorter(const Point& p1, const Point& p2) {
    bool a = p1.y > 0 || (p1.y == 0 && p1.x >= 0);
    bool b = p2.y > 0 || (p2.y == 0 && p2.x >= 0);
    if (a != b) return a;
    long long c = p2.x * (long long)p1.y;
    long long d = p1.x * (long long)p2.y;
    if (c != d) return c < d;
    return p1.length2() < p2.length2();
  }
};

int main() {
  int N;
  cin >> N;
  vector<Point> p(N);
  for (int i = 0; i < N; ++i) cin >> p[i].x >> p[i].y;

  ll eikaku = 0, chokkaku = 0;
  for (int i = 0; i < N; ++i) {
    vector<Point> p2(N - 1);
    for (int j = 0, k = 0; j < N; ++j)
      if (i != j) p2[k++] = p[j] - p[i];
    sort(p2.begin(), p2.end(), Point::Sorter);

    int k = 0, M = N - 1;
    for (int j = 0; j < M; ++j) {
      const Point& q = p2[j];
      while (k < j + M && q.dot(p2[k % M]) >= 0 && q.cross(p2[k % M]) >= 0) ++k;

      eikaku += k - 1 - j;
      if (q.dot(p2[(k - 1) % M]) == 0) eikaku--, chokkaku++;
    }
  }

  ll all = N * (N - 1LL) * (N - 2LL) / 6;
  cout << (eikaku - all * 2) << " " << chokkaku << " "
       << (all * 3 - eikaku - chokkaku) << endl;
}