为什么WA?
查看原帖
为什么WA?
833124
BIOS楼主2023/10/29 17:08
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<double, double> PII;
#define x first
#define y second
const int N = 1e5 + 5;
PII q[N];
int n, stk[N], top, used[N];
PII operator-(PII a, PII b)
{
    return {a.x - b.x, a.y - b.y};
}
double get_dist(PII a, PII b)
{
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
double cross(PII a, PII b)
{
    return a.x * b.y - a.y * b.x;
}
double area(PII a, PII b, PII c)
{
    return cross(b - a, c - a);
}
void Andrew()
{
    sort(q, q + n), memset(used, false, sizeof(used)), top = 0;
    for (int i = 0; i < n; i++)
    {
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
            if (area(q[stk[top - 2]], q[stk[top - 1]], q[i]) < 0)
                used[stk[--top]] = false;
            else
                top--;
        stk[top++] = i, used[i] = true;
    }
    used[0] = false;
    for (int i = n - 1; ~i; i--)
    {
        if (used[i])
            continue;
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) < 0)
            top--;
        stk[top++] = i;
    }
    top--;
}
double caker()
{
    Andrew();
    double res = 0;
    if (top <= 2)
        return get_dist(q[0], q[n - 1]);
    for (int i = 0, j = 2; i < top; i++)
    {
        auto d = q[stk[i]], e = q[stk[i + 1]];
        while (area(d, e, q[stk[j]]) < area(d, e, q[stk[j + 1]]))
            j = (j + 1) % top;
        res = max(res, max(get_dist(d, q[stk[j]]), get_dist(e, q[stk[j]])));
    }
    return res;
}
int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
            cin >> q[i].x >> q[i].y;
        printf("%.9lf\n", caker());
    }
}

这不是一个很裸的旋转卡壳吗...看上去感觉没啥毛病?

2023/10/29 17:08
加载中...