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; }