ABC481 E - Most Brilliant Starry Sky
- サイト
- AtCoder
- コンテスト
- ABC481
- 問題
- E - Most Brilliant Starry Sky
- 難易度
- 1326
平面上に 個の星 があります。原点を通り、どの星も通らない直線を 1 本引き、分けられた 2 つの領域のどちらかを選びます。選んだ領域に含まれる星の個数の最大値を求める問題です。
どの 2 個の星も原点と一直線上に並ぶことはありません。 個のテストケースに答えます( の総和は 以下、)。
半平面を偏角の区間で考える
Section titled “半平面を偏角の区間で考える”原点を通る直線で分けた一方の領域は、偏角(原点から見た向きの角度)が長さ の開区間 に入る点の集まりです。よって、偏角が長さ の区間に入る星の個数の最大値を求めればよいです。
ある領域 が星を含むとき、含まれる星のうち偏角が最小のものを とします。含まれる星の偏角はどれも 以上 未満で、 なので、どれも に入ります。逆に、偏角が に入る星は、 を より少しだけ小さくした領域でちょうど全部含められます。偏角がちょうど の星はないので(原点と一直線上に並ばないため)、 を に十分近くすれば余計な星は入りません。
したがって、各星 について、偏角が に入る星を数え、その最大値が答えです。
星を偏角の順に並べます。偏角は一周すると元に戻るので、偏角に を足した写しを後ろにつなげた長さ の列を作ります。この列で、各 について、偏角が 未満である範囲の右端 を求めると、 が に入る星の個数です。 が増えると も減らないので、尺取り法で全体 で求まります。
計算量は、偏角ソートの です。
偏角は atan2 などの浮動小数点数で求めると、偏角の近い星の比較で誤差が出るおそれがあります。外積を使って比べると、整数だけで正確に比べられます。座標の絶対値は 以下なので、外積は 64 bit 整数に収まります。
C++
#include "shogo-library/base/all"#include "shogo-library/geometry/angle.hpp"#include "shogo-library/utility/container_func.hpp"#include "shogo-library/utility/two-pointers.hpp"
void solve() { LL(N); vec<Angle<ll>> A(N); for (auto &a : A) std::cin >> a; sort(A); rep(i, N) A.push_back(A[i].next_turn()); auto right = two_pointers(2 * N, [&](ll l, ll r) { return A[r] < A[l].opposite(); }); ll ans = 0; rep(l, N) chmax(ans, right[l] - l); print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); LL(T); rep(T) solve();}Angle<ll> はベクトル の偏角を表す型で、周回数 turn を持ち、偏角 として外積で比べます。next_turn() は偏角に を足したもの、opposite() は を足したもの(逆向きのベクトル)です。
sort(A) で偏角の順に並べ、next_turn() で を足した写しを後ろにつなげます。two_pointers(n, can_add) は、各 l について、区間 [l, r) に r を加えてよい(can_add(l, r) が真)間だけ r を伸ばし、伸ばし終えた r を並べた列を返します。ここでは「A[r] の偏角が A[l] の偏角 未満」を条件にしています。
使用ライブラリ:cpp_include@4b58304