poj 1113 Wall(凸包)

Memory: 192K

Time: 47MS

解题思路

题意：

    有个贪心的国王叫他的建筑师给他的城堡周围建个围墙，他要求用最少的石头和劳动力来建造，而且要在距离城堡某个距离之外建造。

    简化一下，就是给出一些点的坐标，然后求能围住所有这些点的最小周长——凸包问题。

 

思路：

        用Graham扫描法：具体见http://blog.chinaunix.net/u3/102624/showart.php?id=2046159

    要求的周长还要比已经求出来的凸包多一段距离，所以结果是凸包周长+一整个圆的周长，圆半径是space，就是围墙离开城堡的距离

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#define N 1003
#define inf 1e-5

typedef struct
{
    int x;
    int y;
}point;
point points[N],chs[N];
int sp;

//如果大于0，说明p1p0在p2p0的下面

long muilt(point p0, point p1, point p2)
{
    return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

double dis(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y));
}

int cmp(const void *p, const void *q)
{
    point a = *(point*)p;
    point b = *(point*)q;
    long k;

    k = muilt(points[0], a, b);
    if(k < 0)
        return 1;
    else if(k == 0 && (dis(a, points[0]) - dis(b, points[0])) > inf )
        return 1;
    else return -1;
}

void Graham(int n)
{
    int i, min, minid;
    
    min = points[0].y;
    minid = 0;
    for(i=1; i<n; i++)
        if(points[i].y < min || points[i].y == min && points[i].x < points[minid].x)
        {
            min = points[i].y;
            minid = i;
        }
    point temp;
    temp = points[0];
    points[0] = points[minid];
    points[minid] = temp;

    qsort(points+1, n-1, sizeof(points[0]), cmp);
    chs[0] = points[n-1];
    chs[1] = points[0];
    sp = 1;
    int    k = 1;
    while(k <= n-1)
    {
        long d = muilt(chs[sp], chs[sp-1], points[k]);
        if(d <= 0)
        {
            sp++;
            chs[sp] = points[k];
            k++;
        }
        else sp--;
    }
}

int main()
{
    int i, j;
    int n, space;

    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &space);
    for(i=0; i<n; i++)
        scanf("%d%d", &points[i].x, &points[i].y);
    Graham(n);
    /*for(i=0; i<=sp; i++)
        printf("%d %d\n", chs[i].x, chs[i].y);*/

    double sum = 0.0;
    for(i=1; i<=sp; i++)
        sum += dis(chs[i-1], chs[i]);
    sum += dis(chs[0], chs[sp]) + 3.1415926535897932384626 * 2 * space;
    printf("%.0lf\n", sum);
    getch();
    return 0;
}