コンテンツにスキップ

ABC481 E - Most Brilliant Starry Sky

サイト
AtCoder
コンテスト
ABC481
問題
E - Most Brilliant Starry Sky
難易度
1326

xyxy 平面上に NN 個の星 (Xi,Yi)(X_i, Y_i) があります。原点を通り、どの星も通らない直線を 1 本引き、分けられた 2 つの領域のどちらかを選びます。選んだ領域に含まれる星の個数の最大値を求める問題です。

どの 2 個の星も原点と一直線上に並ぶことはありません。TT 個のテストケースに答えます(NN の総和は 2×1052 \times 10^5 以下、∣Xi∣,∣Yi∣≤109|X_i|, |Y_i| \le 10^9)。

原点を通る直線で分けた一方の領域は、偏角(原点から見た向きの角度)が長さ π\pi の開区間 (α,α+π)(\alpha, \alpha + \pi) に入る点の集まりです。よって、偏角が長さ π\pi の区間に入る星の個数の最大値を求めればよいです。

ある領域 (α,α+π)(\alpha, \alpha + \pi) が星を含むとき、含まれる星のうち偏角が最小のものを θ\theta とします。含まれる星の偏角はどれも θ\theta 以上 α+π\alpha + \pi 未満で、α<θ\alpha < \theta なので、どれも [θ,θ+π)[\theta, \theta + \pi) に入ります。逆に、偏角が [θ,θ+π)[\theta, \theta + \pi) に入る星は、α\alpha を θ\theta より少しだけ小さくした領域でちょうど全部含められます。偏角がちょうど θ+π\theta + \pi の星はないので(原点と一直線上に並ばないため)、α\alpha を θ\theta に十分近くすれば余計な星は入りません。

したがって、各星 ii について、偏角が [θi,θi+π)[\theta_i, \theta_i + \pi) に入る星を数え、その最大値が答えです。

星を偏角の順に並べます。偏角は一周すると元に戻るので、偏角に 2π2\pi を足した写しを後ろにつなげた長さ 2N2N の列を作ります。この列で、各 ll (0≤l<N)(0 \le l < N) について、偏角が θl+π\theta_l + \pi 未満である範囲の右端 rr を求めると、r−lr - l が [θl,θl+π)[\theta_l, \theta_l + \pi) に入る星の個数です。ll が増えると rr も減らないので、尺取り法で全体 O(N)O(N) で求まります。

計算量は、偏角ソートの O(Nlog⁡N)O(N \log N) です。

偏角は atan2 などの浮動小数点数で求めると、偏角の近い星の比較で誤差が出るおそれがあります。外積を使って比べると、整数だけで正確に比べられます。座標の絶対値は 10910^9 以下なので、外積は 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> はベクトル (x,y)(x, y) の偏角を表す型で、周回数 turn を持ち、偏角 2π⋅turn+[0,2π)2\pi \cdot \mathrm{turn} + [0, 2\pi) として外積で比べます。next_turn() は偏角に 2π2\pi を足したもの、opposite() は π\pi を足したもの(逆向きのベクトル)です。

sort(A) で偏角の順に並べ、next_turn() で 2π2\pi を足した写しを後ろにつなげます。two_pointers(n, can_add) は、各 l について、区間 [l, r) に r を加えてよい(can_add(l, r) が真)間だけ r を伸ばし、伸ばし終えた r を並べた列を返します。ここでは「A[r] の偏角が A[l] の偏角 +π+ \pi 未満」を条件にしています。

使用ライブラリ:cpp_include@4b58304