AtCoder Beginner Contest 033 D - 三角形の分類
角度ソート系の発想は苦手。誤差に敏感な実装も苦手。 とりあえず一定の数を解いて慣れるしかないのだろうか。
D - 三角形の分類
解説
$\frac{n(n-1)(n-2)}{6}$個の三角形の持つ鋭角/直角/鈍角の数を考える。 これらが分かれば鋭角三角形/直角三角形/鈍角三角形の数も分かる。
点をひとつ固定して考える。 その点を頂点とする角は$\frac{(n-1)(n-2)}{2}$個あるが、これをまとめて数えたい。 その点を中心として他の点を角度でソートすれば、角の数を区間の長さとしてまとめて数えることができ、計算量が$n$落ちる。
実装
const long double EPS = 1e-6;
とするとwaする。
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
const long double EPS = 1e-10;
int main() {
ll n; cin >> n;
vector<int> y(n), x(n);
repeat (i,n) cin >> x[i] >> y[i];
ll acute_angle = 0;
ll right = 0;
repeat (i,n) {
vector<long double> angles;
repeat (j,n) if (j != i) angles.push_back(atan2l(y[j] - y[i], x[j] - x[i]));
sort(angles.begin(), angles.end());
repeat (j,n-1) angles.push_back(angles[j] + 2*M_PI);
int k = 0;
repeat (j,n-1) {
while (angles[k+1] - angles[j] < M_PI/2 - EPS) ++ k;
acute_angle += k - j;
assert (M_PI/2 - EPS <= angles[k+1] - angles[j]);
if (angles[k+1] - angles[j] < M_PI/2 + EPS) ++ right;
}
}
ll all_angle = n*(n-1)*(n-2)/6;
ll obtuse = 3*all_angle - acute_angle - right;
ll acute = all_angle - right - obtuse;
cout << acute << ' ' << right << ' ' << obtuse << endl;
return 0;
}