计算几何

用计算机解决几何问题，显然计算机（至少在 OI/CPC 中）是不能处理复杂的图形的，所以解决方法和数学中解析几何类似。

直线

直线有四种表示方法：斜截式，点斜式，两点式，一般式。
斜截式：\(y=kx+b\)，其中 \(k\) 为直线的斜率，\(b\) 为截距。两点（设为\((x_1,y_1),(x_2,y_2)\)）确定一条直线，则这条直线的斜率 \(k = \frac{x_1-x_2}{y_1-y_2}\)。注意当直线平行于 \(y\) 轴时不能用斜截式表示。
点斜式：对求斜率公式移项，把一个点当任意点，另一个点坐标已知（设为\((x_0,y_0)\)），则有 \(y - y_0 = k (x - x_0)\)

例题：luogu P1142 轰炸

先枚举直线（枚举两点计算斜率），然后计算有多少点在这条直线上（带入点斜式公式），取最大值即可。
参考代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 705;
const double eps = 1e-8;

int n, ans = 1;

int x[N], y[N];

bool dcmp(double x, double y)
{
    return abs(x - y) <= eps;
}

double calc_k(int x_1, int y_1, int x_2, int y_2)
{
    return double(y_1 - y_2) / (x_1 - x_2);
}

signed main()
{
    ios::sync_with_stdio(false);
#ifdef DEBUG
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow.

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (x[i] != x[j])
            {
                int res = 0;
                double k = calc_k(x[i], y[i], x[j], y[j]);
                for (int p = 1; p <= n; p++)
                    res += dcmp(y[p] - y[i], k * (x[p] - x[i]));
                ans = max(ans, res);
            }
            else // 平行于 y 轴的直线
            {
                int res = 0;
                for (int p = 1; p <= n; p++)
                    res += x[p] == x[i];
                ans = max(ans, res);
            }

    cout << ans << endl;

    return 0;
}

凸包