This problem can be solved with a randomized algorithm fast enough with sufficiently high probability.

Suppose that there exists a line \(ax+by+c=0\) passing through more than half of the lines. Then, there are at least \(\frac{N+1}{2}\) points on this line. Thus, if you randomly choose two out of the \(N\) points, the probability that both of them are located on the line is

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

In other words, \(p_1\) and \(p_2\) are both on the line with probability \(\frac{1}{4}\) or higher.
Also, when you choose different points \(p_1\) and \(p_2\), the line passing through both of them is unique.
Therefore, if the answer exists, the following randomized algorithm \((\ast)\) reports the correct answer with probability \(\frac{1}{4}\) or higher:

• Choose two points \(p_1\) and \(p_2\) out of the \(N\) points at random, and take the line \(l\) passing through both of them. Inspect whether \(l\) passes through more than half of the lines, and print that \(l\) if it does.\(\cdots(\ast)\)

The algorithm \((\ast)\) alone fails with probability \(\frac{3}{4}\), which is too high, so we modify it as follows: execute \((\ast)\) \(T\) times. If no conforming line was found, then report No.

Since \((\ast)\) runs in \(\mathrm{O}(N)\), this algorithm runs in \(\mathrm{O}(TN)\), so the probability of ending up in a wrong answer is no greater than \(\left(\frac{3}{4}\right)^T\). If you pick \(T=100\) for example, the failure probability is \(3.2 \times 10^{-13}\), which is small enough. This algorithm is fast and accurate enough.

Note that the line passing through two points \(p_1 = (x_1, y_1)\) and \(p_2 = (x_2, y_2)\) can be expressed as

\[ \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} \]

Under the constraints, the absolute value of \((y_1 - y_2) x + (x_2 - x_1)y + x_1 y_2 - x_2 y_1\) never exceeds \(10^{18}\) (including during the computation), so we may compute using \(64\)-bit integers.

#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];

  // Type that returns a pseudo-random integer, with seed 50.
  // Caution is needed in hack-able contests like CodeForces.
  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";
}