首页 > 代码库 > POJ 1113 - Wall 凸包模板

POJ 1113 - Wall 凸包模板

2024-08-16 16:00:06   219人阅读

此题为凸包问题模板题，题目中所给点均为整点，考虑到数据范围问题求norm()时先转换成double了，把norm()那句改成<vector>压栈即可求得凸包。

初次提交被坑得很惨，在GDB中可以完美运行A掉，到OJ上就频频RE（此处应有黑人问号）

后来发现了问题，原因是玩杂耍写了这样的代码

struct point {
    int x, y;
    point (){
        scanf("%d%d", &x, &y);
    }
    ...
}pt[MAXN];

于是乎，在swap

void swap(point &a, point &b){
    point t = a;
    a = b;
    b = t;
}

的时候临时变量把数据读进去了，GG

 //Ps. 我感觉这个代码高亮比上次的好看

//POJ1113
//凸包
//AC 2016.10.13

#include "cstdio"
#include "cstdlib"
#include "cmath"
#include "iostream"
#define MAXN 1010
const double pi = acos(-1.0);

double sqr(double x){
    return x * x;
}

struct point {
    int x, y;
    point (){}
    point (int X, int Y): x(X), y(Y) {}
    double norm(){
        return sqrt(sqr(x) + sqr(y));
    }
    friend bool operator < (const point &p1, const point &p2){
        return (p1.x < p2.x)||(p1.x == p2.x)&&(p1.y < p2.y);
    }
    friend bool operator > (const point &p1, const point &p2){
        return (p1.x > p2.x)||(p1.x == p2.x)&&(p1.y > p2.y);
    }
    friend point operator >> (const point &p1, const point &p2){
        return point(p2.x - p1.x, p2.y - p1.y);
    }
    friend int operator ^ (const point &p1, const point &p2){
        return p1.x * p2.y - p1.y * p2.x;
    }
}pt[MAXN];

void swap(point &a, point &b){
    point t = a;
    a = b;
    b = t;
}

int main(){
    int n, l;
    freopen("fin.c", "r", stdin);
    scanf("%d%d", &n, &l);
    for (int i = 0; i < n; i++){
        scanf("%d%d", &pt[i].x, &pt[i].y);
        for (int j = i; j && (pt[j - 1] > pt[j]); j--)
            swap(pt[j - 1], pt[j]);
    }
    int cur = 0;
    double res = 0;
    while (1){
        int tmp = - 1;
        for (int i = 0; i < n; i++)
            if (i != cur){
                if (tmp == - 1)
                    tmp = i;
                else if (((pt[cur] >> pt[i]) ^ (pt[cur] >> pt[tmp])) > 0)
                    tmp = i;
            }
        res += (pt[cur] >> pt[tmp]).norm();
        cur = tmp;
        if ((tmp == - 1)||(!tmp)) break;
    }
    printf("%d\n", (int)(res + 2 * pi * l + 0.5));
    return 0;
}

 

POJ 1113 - Wall 凸包模板


联系
我们