[ARC173] B - Make Many Triangles
考察
1. N <= 300と少ない。O(N^2)くらい計算できる
2. 同一直線上にある点集合Xと、そうじゃない点集合Yがわかればうれしい。
3. Xの3点を結んだ3角形は直線になってしまうからいけない。どこか1つでもYの点を組み合わせれば3角形が作れることが分かる。
4. Xの最大数を求めたら、YはN - {Xの個数}で求まる。
5. 答えはmin(N / 3, Y)になる。
XがたくさんあればYの個数だけ三角形が作れるし、
Yがたくさんあれば、自由に三角形を構築でき、最大N/3個まで作れる。
6. どうやって点集合Xの最大数を求めよう?
7. 点i(0~N)を原点とみなした場合の、その他の点の傾きを調べる。同じ傾きの最大数がXの候補になる。
実装
int main()
{
cincout();
ll N;
cin >> N;
vector<ll> X(N), Y(N);
rep(i, N) cin >> X[i] >> Y[i];
ll mx_cnt = 0;
rep(i, N) // 原点iとする
{
ll x0 = 0;
map<ld, ll> mp;
rep(j, N)
{
if (i == j) continue;
ll x = X[i] - X[j];
ll y = Y[i] - Y[j];
if (x == 0)
{
x0++;
}
else
{
ld k = (ld)y / x;
mp[k]++;
}
}
for (auto [d, cnt] : mp)
chmax(mx_cnt, cnt + 1);
chmax(mx_cnt, x0 + 1);
}
// 1. 最大でN / 3個の三角形ができる
// 2. mx_cntの3点では直線になってしまう。N - mx_cntの集合Yから1つ選ぶ必要がある。
ll ans = min(N - mx_cnt, N / 3);
cout << ans << endl;
}
この記事が気に入ったらサポートをしてみませんか?