题解：P4636 [SHOI2011] 直线拟合

pigeonteam · 2024-11-22 16:13:17 · 题解

首先吐槽一句，为什么题解区没有正解。
题面简述：在二维平面上有 n 个点，求一条线到所有点的距离最小，并输出最小距离。
不难发现，这其实是一个旋转卡壳，只不过求的东西似乎和板子不太一样。
我们可以在求出凸包以后对于每一个相邻点对求出以这两个点为底边到另外的点构成的三角形的最大高。
答案就是所有最大高的最小值除以二（原因看代码注释）。
然后就是这道题卡精度，需要开 long double。
下面是代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef double db;
#define double long double

const double pi = 3.141592653589793l; // 基本上oi里这个精度就够了

struct point
{
    double x, y, arctan;
    point() {}
    point(double x, double y) : x(x), y(y) {}
    double atan(point &rhs) // 顺时针弧度
    {
        arctan = atan2(y - rhs.y, x - rhs.x);
        return arctan < 0 ? arctan += 2 * pi : arctan;
    }
    double operator-(point &rhs) const // 获取两个点之间的距离
    {
        double temp_x = x - rhs.x;
        double temp_y = y - rhs.y;
        return sqrt(temp_x * temp_x + temp_y * temp_y); // 勾股定理
    }
    friend ostream &operator<<(ostream &out, point &rhs)
    {
        out << '{' << rhs.x << ", " << rhs.y << '}';
        return out;
    }
};

vector<point> g;
int n;

inline void tubao()
{
    for (auto &i : g)
        i.atan(*g.begin());
    sort(g.begin() + 1, g.end(), [](point &a, point &b) -> bool
         { return a.arctan < b.arctan; }); // 按弧度排序
    vector<point> ans;
    for (auto &i : g)
    {
        while (ans.size() > 1)
        {
            i.atan(*ans.rbegin());
            ans.rbegin()->atan(*(ans.rbegin() + 1));
            if (i.arctan - ans.rbegin()->arctan <= -1e-12l)
                ans.pop_back();
            else
                break;
        }
        ans.emplace_back(i);
    }
    ans.swap(g); // g数组变成了凸包上的点
    // 由于vector内部是指针，所以swap是O(1)的
}

double get_min_maxlen() // 旋转卡壳
{
    auto get_len = [](point &a, point &b, point &c) -> double
    {
        double len_down = a - b;
        double len1 = a - c;
        double len2 = b - c;
        double p = (len_down + len1 + len2) / 2;
        double siz = sqrt(p * (p - len_down) * (p - len1) * (p - len2)); // 海伦公式
        double lenth = (siz * 2) / len_down;                             // c点到a,b所成线段的距离
        return lenth;                                                    // 别看定义了这么多变量，我们要相信编译器的优化
    };

    double ans(1e200l); // 将答案赋值为一个极大值
    size_t len = g.size();
    auto it = g.begin() + 2;
    for (int i = 1; i < len; ++i)
    {
        while (1)
        {
            if (get_len(g[i - 1], g[i], *it) - get_len(g[i - 1], g[i], *(it + 1 == g.end() ? g.begin() : it + 1)) < -1e-12l)
            {
                ++it;
                if (it == g.end())
                    it = g.begin();
            }
            else
                break;
        }
        ans = min(ans, get_len(g[i - 1], g[i], *it));
    }
    // 特别处理第一个和最后一个
    while (1)
    {
        if (get_len(*g.begin(), *g.rbegin(), *it) - get_len(*g.begin(), *g.rbegin(), *(it + 1 == g.end() ? g.begin() : it + 1)) < -1e-12l)
        {
            ++it;
            if (it == g.end())
                it = g.begin();
        }
        else
            break;
    }
    ans = min(ans, get_len(*g.begin(), *g.rbegin(), *it));
    return ans;
}

int main()
{
    scanf("%d", &n);
    g.reserve(n);
    for (int i = 0; i < n; ++i)
    {
        db x, y;
        scanf("%lf%lf", &x, &y);
        g.emplace_back(x, y);
    }

    sort(g.begin(), g.end(), [](point &a, point &b) -> bool
         { return a.y == b.y ? a.x > b.x : a.y < b.y; }); // 用lambda或重载运算符会比传入函数快

    // 二维凸包
    tubao();

    printf("%.2lf\n", (db)(get_min_maxlen() / 2)); // 距离最小的直线垂直平分最短直径
    return 0;
}