この問題は 乱択アルゴリズム を使用することで高速かつ十分高確率で問題を解くことが出来ます。

過半数の点を通る直線 \(ax+by+c=0\) が存在すると仮定します。この時、直線上には \(\frac{N+1}{2}\) 個以上の点が存在します。よって、\(N\) 点からランダムに異なる 2 点 \(p_1, p_2\) を選んだとすると、両方の点が直線上に存在する確率は

\[\frac{\frac{N+1}{2}}{N} \cdot \frac{\frac{N+1}{2}-1}{N-1} = \frac{N+1}{4N} \gt \frac{1}{4}\]

です。すなわち、\(\frac{1}{4}\) 以上の確率で \(p_1, p_2\) はともに直線上に存在します。
また、異なる 2 点 \(p_1, p_2\) を選んだ時に、両方の点を通る直線は一意に定まります。
よって、答えが存在する時は次の乱択アルゴリズム \((\ast)\) が \(\frac{1}{4}\) の確率で正答を返します。

• \(N\) 点の中から 2 点 \(p_1, p_2\) をランダムに選んで、\(p_1, p_2\) を両方通る直線 \(l\) を取ってくる。\(l\) が過半数の点を通るか調べて、もし通るならばその \(l\) を出力する。\(\cdots(\ast)\)

\((\ast)\) のままでは誤答する確率が \(\frac{3}{4}\) と非常に高いので次のように改善します：\((\ast)\) を \(T\) 回行う。条件を満たす直線を発見できなかった時は No を返す。

\((\ast)\) は \(\mathrm{O}(N)\) で動作するので、このアルゴリズムは \(\mathrm{O}(TN)\) で動作して、誤答する確率は解が存在する場合で高々 \(\left(\frac{3}{4}\right)^T\) になります。よって \(T=100\) 程度を取れば誤答確率が約 \(3.2 \times 10^{-13}\) と十分低いアルゴリズムを構成出来て、これは十分高速かつ正確です。

なお、2 点 \(p_1 = (x_1, y_1), p_2 = (x_2, y_2)\) を通る直線は

\[ \begin{aligned} &(x - x_1) (y - y_2) = (x - x_2) (y - y_1) \\ &\iff (y_1 - y_2) x + (x_2 - x_1)y + x_1 y_2 - x_2 y_1 = 0 \end{aligned} \]

と表すことが出来ます。制約下において \((y_1 - y_2) x + (x_2 - x_1)y + x_1 y_2 - x_2 y_1\) は(計算過程の値も含めて) 絶対値が \(10^{18}\) 以下に収まるので 64 bit 整数を用いて計算して問題ないです。

#include <iostream>
#include <random>
using namespace std;
using ll = long long;

ll N, X[500500], Y[500500];

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];

  // 疑似乱数を返す型。58 はシード
  // CodeForces などの hack 可能なコンテストでは使用に注意が要る
  mt19937_64 rng(58);

  int T = 100;
  for (int t = 0; t < T; t++) {
    int i, j;
    do {
      i = rng() % N, j = rng() % N;
    } while (i == j);
    ll a = Y[i] - Y[j];
    ll b = X[j] - X[i];
    ll c = X[i] * Y[j] - X[j] * Y[i];
    int num = 0;
    for (int k = 0; k < N; k++) num += a * X[k] + b * Y[k] + c == 0;
    if (num * 2 > N) {
      cout << "Yes\n";
      cout << a << " " << b << " " << c << "\n";
      return 0;
    }
  }
  cout << "No\n";
}