2012-0021

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

占坑,By FFheyy

就是一个凸包，只需要取上半部分，从左往右扫一遍即可。
{{{
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1000001;

double x[MAXN], y[MAXN];
int a[MAXN],n;

double dis(const int a, const int b) 
{
    return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}

double check(const int a, const int b, const int c) 
{
    return (x[b] - x[a]) * (y[c] - y[a]) - (x[c] - x[a]) * (y[b] - y[a]);
}

int main() 
{
    int i, j, k;
    double ans;

    while (scanf("%d", &n)!=EOF) 
        {
        for (i=0; i<n; ++i) scanf("%lf%lf", x+i, y+i);
        for (k=i=0; i<n; ++i) 
                {
            for (; k>=2 && check(a[k-2], a[k-1], i)>=0; --k);
            a[k++] = i;
        }
        for (ans=0,i=0; i+1<k; ++i) ans += dis(a[i], a[i+1]);
        printf("%.2lf\n", ans);
    }

    return 0;
}
}}}

占坑,By FFheyy

就是一个凸包，只需要取上半部分，从左往右扫一遍即可。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000001;
double x[MAXN], y[MAXN];
int a[MAXN],n;
double dis(const int a, const int b) 
{
    return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
double check(const int a, const int b, const int c) 
{
    return (x[b] - x[a]) * (y[c] - y[a]) - (x[c] - x[a]) * (y[b] - y[a]);
}
int main() 
{
    int i, j, k;
    double ans;
    while (scanf("%d", &n)!=EOF) 
        {
        for (i=0; i<n; ++i) scanf("%lf%lf", x+i, y+i);
        for (k=i=0; i<n; ++i) 
                {
            for (; k>=2 && check(a[k-2], a[k-1], i)>=0; --k);
            a[k++] = i;
        }
        for (ans=0,i=0; i+1<k; ++i) ans += dis(a[i], a[i+1]);
        printf("%.2lf\n", ans);
    }
    return 0;
}