Andrew求调
查看原帖
Andrew求调
742017
zhangxiao666楼主2024/1/11 21:20
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, top;
double ans;
struct Vec
{
    double x, y;
}a[N], sta[N];

bool cmp(Vec a1, Vec a2)
{
    return a1.y != a2.y ? a1.y > a2.y : a1.x < a2.x;
}

double chaji(Vec a1, Vec a2)
{
    return a1.x * a2.y - a1.y * a2.x;
}

double check(Vec a1, Vec a2, Vec now)
{
    Vec A, B;
    A.x = a2.x - a1.x, A.y = a2.y - a1.y;
    B.x = now.x - a1.x, B.y = now.y - a1.y;
    return chaji(A, B);
}

double dis(Vec a1, Vec a2)
{
    return sqrt((a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y));
}

double work()
{
    sta[++top] = a[1], sta[++top] = a[2];
    for(int i = 3; i <= n; i++)
    {
        while(top >= 2 && check(sta[top - 1], sta[top], a[i]) <= 0) top--;
        sta[++top] = a[i];
    }
    for(int i = 2; i <= top; i++) ans += dis(sta[i], sta[i - 1]);
    top = 0;
    sta[++top] = a[1], sta[++top] = a[2];
    for(int i = 3; i <= n; i++)
    {
        while(top >= 2 && check(sta[top], sta[top - 1], a[i]) >= 0) top--;
        sta[++top] = a[i];
    }
    for(int i = 2; i <= top; i++) ans += dis(sta[i], sta[i - 1]);
    return ans;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp);
    printf("%.2lf\n", work());
    return 0;
}
2024/1/11 21:20
加载中...