決定的に解く方法
平面上の $N$ 個の点のうち、過半数の点を通るような直線が存在するかを調べる問題です。
公式解説に示されたように、ランダムに2点を選んで直線を作り、その直線を通る点の数を数えるという戦略があります。一方、この記事では乱択を使わない決定的に解く方法を記します。
$N$ 個の点のうち過半数を通る直線 $L$ が存在すると仮定します。直線 $L$ が通る点の数を$k$とします。過半数であることから、$2k\gt N$ が成立します。
次に、$N$ 個の点を $2$ つの部分集合 $S$ 及び $T$ に分割することを考えます。
このとき、直線$L$は以下の条件の少なくとも $1$ つを満たします。
- $L$は$S$に含まれる点の過半数を通る。
- $L$は$T$に含まれる点の過半数を通る。
証明
仮に、直線 $L$ が集合 $S$ と $T$ のいずれの過半数も通らないと仮定します。
$S$ において $L$ が通る点の数を $k_S$、$T$ においては $k_T$ とします。$L$ が通る点の総数は $k_S + k_T = k$ です。
仮定より、$2k_S\leq|S|$ と $2k_T\leq|T|$ がいえます。よって両辺を足すと、$2k_S+2k_T\leq|S|+|T|=N$になり、つまり $2k\leq N$ が成り立ちます。
しかし、$L$ は過半数を通るので $2k\gt N$ が成立しており、これは矛盾します。
したがって、$L$ は $S$ または $T$ のどちらかで過半数を通らなければなりません。
この性質から、過半数の点を通る直線 $L$ が存在するなら、$L$ は分割した部分集合のどこかに現れることが保証されます。
したがって、分割統治の要領で $L$ を求めることができます。
- 点集合を半分ずつに分割して再帰的に解く。
- 各「$2$ 個以上の点からなる」部分集合について、その部分集合の過半数を通る直線候補を全列挙する。
- 見つかった候補が全体の過半数を通るか判定し、結果を出力する。
ステップ2では候補を全列挙していますが、$n\geq2$ 個の相異なる点のうち過半数を通る直線はたかだか $3$ 本しかありません。したがって、計算量は各レベルで $\mathcal{O}(N)$、深さは $\mathcal{O}(\log N)$ なので、全体で $\mathcal{O}(N\log N)$ 時間で解けます。
逆にそのような直線 $L$ が存在しない場合について考えます。対偶により、どの部分集合でも過半数を通る直線がなければ、全体の過半数を通る直線は存在しません。
よって、点を部分集合に分割し、各部分集合について過半数を通る直線が存在するか調べ、もし存在しても $\mathcal{O}(N)$ 時間で全体の過半数を通るか判定できるので、結局過半数を通る直線が存在しなくても分割統治で問題を解くことができます。
過半数を通る直線の本数の上界の証明
$2$ つの異なる直線が共有する点はたかだか $1$ 個です。
もし $n$ 個の点の過半数を通るような異なる直線が $2$ 本あれば、どちらかの直線が通る点は少なくとも $2\lfloor n/2+1\rfloor-1\leq n$ 個あります。
$n$ が偶数の場合、点の個数は最低でも $2\lfloor n/2+1\rfloor-1=n+1$ になりますが、これは点が $n$ 個しかない事実と矛盾するので、過半数を通る直線は最大 $1$ 個しかありません。
$n$ が奇数の場合、点の個数は最低 $2\lfloor n/2+1\rfloor-1=n$ なので、過半数を通る直線が $2$ 本存在することもあります。
$3$ 本の相異なる、過半数を通る直線について考えます。$3$ 本の直線のうち、$2$ 本以上が通る点は最大 $3$ 個なので、いずれかの直線が通る点は少なくとも $3\lfloor n/2+1\rfloor-3\leq n$ 個あります。しかしこの不等式が成立するのは $n=3$ の場合のみであって、$n\geq5$ なら矛盾することが確認できます。
$n=3$ の場合、過半数を通る直線の選び方は最大 $3$ 通りしかないので、どの $n\geq2$ についても過半数を通る直線はたかだか $3$ 本しかありません。
実装例（Python）
N = int(input())
points = [tuple(int(x) for x in input().split()) for _ in range(N)]
x = [p[0] for p in points]
y = [p[1] for p in points]
def find_majority_lines(l, r):
if r - l <= 1:
return []
if r - l == 2:
a = y[l + 1] - y[l]
b = x[l] - x[l + 1]
c = -a * x[l] - b * y[l]
return [(a, b, c)]
if r - l == 3:
result = []
for k in range(3):
a = y[l + (k+1)%3] - y[l + k]
b = x[l + k] - x[l + (k+1)%3]
c = -a * x[l + k] - b * y[l + k]
result.append((a, b, c))
return result
result = []
mid = (l + r) // 2
max_num_lines = 2 if (r - l) % 2 == 1 else 1
for subresult in (find_majority_lines(l, mid), find_majority_lines(mid, r)):
for a, b, c in subresult:
count = sum(1 for i in range(l, r) if a * x[i] + b * y[i] + c == 0)
if count * 2 <= r - l:
continue
if result:
ra, rb, rc = result[0]
if a * rb == b * ra and a * rc == c * ra and b * rc == c * rb:
continue
result.append((a, b, c))
if len(result) == max_num_lines:
return result
return result
result = find_majority_lines(0, N)
if result:
print("Yes")
print(*result[0])
else:
print("No")
A deterministic solution
In this problem, we are asked to determine whether there exists a line that passes through more than half of $N$ points on a plane.
The official editorial provides a solution that randomly chooses two points to form a line and counts the number of points on the line. On the other hand, we will introduce a deterministic solution that does not rely on randomization.
Suppose there exists a line $L$ that passes through more than half of the $N$ points. Let $k$ be the number of points that $L$ passes through. Since $L$ passes through more than half of the points, we obtain $2k\gt N$.
Next, consider partitioning the $N$ points into two subsets $S$ and $T$. Here, $L$ satisfies at least one of the following properties:
- $L$ passes through more than half of the points in $S$.
- $L$ passes through more than half of the points in $T$.
Proof
Suppose line $L$ passes through at most half of the points in $S$ and at most half of the points in $T$.
Let $k_S$ and $k_T$ be the number of points that $L$ passes through in $S$ and $T$, respectively. The total number of points $L$ passes through is $k_S+k_T=k$.
From our supposition, we obtain $2k_S\leq|S|$ and $2k_T\leq|T|$. Adding both equations yields $2k_S+2k_T\leq |S|+|T|=N$, so $2k\leq N$.
However, this contradicts the fact that $2k\gt N$, so the supposition is false.
Thus, $L$ must pass through more than half of the points in at least one of the subsets.
Using this property, if $L$ passes through more than half of the $N$ points, it must also pass through some of the partitioned subsets.
Thus, we can implement a divide-and-conquer solution to find $L$.
- Partition the points into halves and solve for each subset recursively.
- For each subset with at least two points, enumerate all lines that pass through more than half of the subset as candidates.
- Check if any candidate passes through more than half of the points in the original set and output the result.
In step 2, there are at most $3$ distinct candidates for each subset with at least two points, so this solution runs in $\mathcal{O}(N)$ time for each of the $\mathcal{O}(\log N)$ levels. The time complexity of our solution is $\mathcal{O}(N\log N)$.
Now suppose no such line $L$ exists. By contraposition, if no lines pass through at least half of any subsets, there also does not exist a line that passes through at least half of the original $N$ points.
We can still partition points into subsets and determine if any candidates exist, and check if each of the candidates passes through more than half of the $N$ points in $\mathcal{O}(N)$ time. Hence, our divide-and-conquer solution is correct regardless of whether $L$ exists or not.
Proof on the upper bound of the number of candidates
The number of points shared by two distinct lines is at most $1$. If both of these lines pass through more than half of $n$ points in a subset, the total number of points on either of these lines is at least $2\lfloor n/2+1\rfloor-1\leq n$.
If $n$ is even, the number of points is at least $2\lfloor n/2+1\rfloor-1=n+1$, but this contradicts the fact that there are only $n$ points. Thus, there can only be at most one line passing through more than half of the points.
If $n$ is odd, the number of points is at least $2\lfloor n/2+1\rfloor-1=n$, so there can indeed exist two distinct lines passing through more than half of the points.
Now consider three distinct lines that pass through more than half of the points. Since the number of points shared by at least two of the three lines is at most $3$, the number of points on any of the three lines is at least $3\lfloor n/2+1\rfloor-3\leq n$. However, this inequality only holds for $n=3$, ruling out the possibility for $n\geq5$.
The number of lines that pass through more than half of the $n=3$ points is at most $3$. Thus, for all $n\geq2$, the number of distinct lines passing through more than half of $n$ points is at most $3$.
Implementation in Python
N = int(input())
points = [tuple(int(x) for x in input().split()) for _ in range(N)]
x = [p[0] for p in points]
y = [p[1] for p in points]
def find_majority_lines(l, r):
if r - l <= 1:
return []
if r - l == 2:
a = y[l + 1] - y[l]
b = x[l] - x[l + 1]
c = -a * x[l] - b * y[l]
return [(a, b, c)]
if r - l == 3:
result = []
for k in range(3):
a = y[l + (k+1)%3] - y[l + k]
b = x[l + k] - x[l + (k+1)%3]
c = -a * x[l + k] - b * y[l + k]
result.append((a, b, c))
return result
result = []
mid = (l + r) // 2
max_num_lines = 2 if (r - l) % 2 == 1 else 1
for subresult in (find_majority_lines(l, mid), find_majority_lines(mid, r)):
for a, b, c in subresult:
count = sum(1 for i in range(l, r) if a * x[i] + b * y[i] + c == 0)
if count * 2 <= r - l:
continue
if result:
ra, rb, rc = result[0]
if a * rb == b * ra and a * rc == c * ra and b * rc == c * rb:
continue
result.append((a, b, c))
if len(result) == max_num_lines:
return result
return result
result = find_majority_lines(0, N)
if result:
print("Yes")
print(*result[0])
else:
print("No")