【AtCoder】ABC 481 E - Most Brilliant Starry Sky

2026-10-26

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/数学/図形/座標幾何 AtCoder/数学/偏角ソート AtCoder尺取り法競技プログラミング

E - Most Brilliant Starry Sky

E - Most Brilliant Starry Sky

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1326 / NoviSteps: 1D / 配点: 450 点

問題概要

$xy$ 平面上に $N$ 個の星があり、 $i$ 個目の星は、座標が $(X_i,Y_i)$ である。

原点を通りどの星も通らない直線を $1$ 本引き、その直線によって分けられる二つの領域のうちどちらか一方の領域を選ぶとき、選んだ領域に含まれる星の個数としてありうる最大値を求めよ。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1 \le T \le 2 \times 10^5$
$1 \le N \le 2 \times 10^5$
全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
$-10^9 \le X_i,Y_i \le 10^9$
$(X_i,Y_i) \ne (0,0)$
$(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)$
どの相異なる $2$ 個の星についても、それらと原点が一直線上に並ぶことはない
入力される値はすべて整数

考察

原点を通る直線で平面を分割すると、選んだ領域は角度 $180^\circ$ の開半平面となる。

したがって、問題は次のように言い換えられる。

偏角が連続する $[0, \pi]$ 未満の範囲に含まれる点の個数の最大値を求めよ。

ここで、 $N$ 個の点を偏角ソートしておき、それぞれの点の角度を

\theta_1 < \theta_2 < \cdots < \theta_{N}

とすると、各 $l = 1, 2, \ldots, N$ に対して、求めたいのは

\theta_r - \theta_l < \pi

を満たす最大の $r$ である。

$l$ が増加すると、 $\theta_l+\pi$ も単調に増加するので、尺取り法で全体を $O(N)$ で処理することができる。

実装時は、偏角ソート後の配列を2周分に拡張しておけば、偏角が $2\pi$ をまたぐ場合も連続した区間として扱えるので楽をすることができる。

また、2点の偏角差が $2\pi$ 未満のとき、その 偏角差が $\pi$ 未満である条件は「2点の外積が正であること」または「2点が同じ方向を向いていること」 と言い換えられる。

本問では、制約から原点と相異なる2点が一直線上に並ばないため、開始点自身を含めて、以降の点は外積が正の間だけ数えればよい。

計算量は、偏角ソート部分がボトルネックとなって、 $O(N \log N)$ である。

なお、偏角ソートする際は外積を使った方が整数で計算できるので、atan2を使うよりも安全である。

ここでの実装は ABC442-E の公式解説で挙げられていたものをそのまま流用している。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8. 
9.template <typename T>
10.inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
11. 
12.// ======================================== //
13. 
14.struct point {
15.    ll x, y;
16.};
17. 
18.ll cross(const point& a, const point& b) {
19.    return a.x * b.y - a.y * b.x;
20.}
21.bool cmp(const point& a, const point& b) {
22.    ll ah = (a.y < 0 or (a.y == 0 and a.x < 0));
23.    ll bh = (b.y < 0 or (b.y == 0 and b.x < 0));
24.    if (ah != bh) return ah < bh;
25.    return cross(a, b) > 0;
26.}
27.void argument_sort(vector<point>& points) {
28.    sort(all(points), cmp);
29.}
30. 
31.int solve() {
32.    int N;
33.    cin >> N;
34.    vector<point> points(N);
35.    rep(i, 0, N) cin >> points[i].x >> points[i].y;
36. 
37.    argument_sort(points);
38. 
39.    rep(i, 0, N) points.push_back(points[i]);
40. 
41.    int ans = 0;
42.    int r = 0;
43.    rep(l, 0, N) {
44.        r = max(r, l + 1);
45.        while (r < l + N && cross(points[l], points[r]) > 0) r++;
46. 
47.        chmax(ans, r - l);
48.    }
49. 
50.    return ans;
51.}
52. 
53.int main()
54.{
55.    int T;
56.    cin >> T;
57. 
58.    while (T--) {
59.        cout << solve() << endl;
60.    }
61. 
62.    return 0;
63.}

https://atcoder.jp/contests/abc481/submissions/80333194

実装時間: 30分

コメント

偏角ソート、いい加減ライブラリ化しよう(自戒)。