1392.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define maxLength 1000
int stack[maxLength];
int top;
typedef struct Tpoint{
    int x;
    int y;
}Tpoint;
Tpoint p[maxLength];
void swap(Tpoint p[], int i, int j){
    Tpoint temp;
    temp = p[i];
    p[i] = p[j];
    p[j] = temp;
}
double multiply(Tpoint p1, Tpoint p2, Tpoint p0){
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
double distance(Tpoint p1, Tpoint p2){
    return sqrt(double(p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y));
}
int cmp(const void *a, const void *b){
    Tpoint *c = (Tpoint*)a;
    Tpoint *d = (Tpoint*)b;
    double k = multiply(*c, *d, p[0]);
    if (k < 0)
        return 1;
    else if (k == 0 && distance(*c, p[0]) >= distance(*d, p[0]))
        return 1;
    else
        return -1;
}
void grahamScan(int n){
    int u = 0;
    for (int i = 1; i < n; i++)
        if ((p[i].y < p[u].y) ||(p[i].y == p[u].y && p[i].x < p[u].x))
            u = i;
    swap(p, 0, u);
    qsort(p+1, n-1, sizeof(p[0]), cmp);
    stack[0] = 0;
    stack[1] = 1;
    stack[2] = 2;
    top = 2;
    for (int j = 3; j < n; j++){
        while (multiply(p[j], p[stack[top]], p[stack[top-1]]) > 0){
            top--;
            if (top == 0)
                break;
        }
        top++;
        stack[top] = j;
    }
}
double length(int n){
    double len = 0;
    for (int i = 0; i < n; i++)
        len += distance(p[stack[i]], p[stack[(i + 1) % n]]);
    return len;
}
int main()
{
    int n;
    while (scanf("%d", &n)==1&&n){
        for (int i= 0; i < n; i++)
            scanf("%d%d", &p[i].x, &p[i].y);
        if (n == 1){
            printf("0.00\n");
            continue;
        }
        if (n == 2){
            printf("%.2lf\n", distance(p[0], p[1]));
            continue;
        }
        grahamScan(n);
        printf("%.2lf\n", length(top + 1));
    }
    return 0;
}