wall(计算几何).cpp

杭电acm解题报告2001---2099.

//此题给的多边形可能是凹的
//先求出围住城堡的多边形，然后在保持距离的条件下贴着城堡
//最小长度=2*Pi*L + 凸包边长
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;
typedef double TYPE;

#define Abs(x) (((x)>0)?(x):(-(x)))
#define Sgn(x) (((x)<0)?(-1):(1))
#define Max(a,b) (((a)>(b))?(a):(b))
#define Min(a,b) (((a)<(b))?(a):(b))

#define Epsilon 1e-10
#define Infinity 1e+10
#define Pi 3.14159265358979323846


struct POINT
{
    TYPE x;
    TYPE y;
    TYPE z;
    POINT() : x(0), y(0), z(0) {};
    POINT(TYPE _x_, TYPE _y_, TYPE _z_ = 0) : x(_x_), y(_y_), z(_z_) {};
};

struct POLY
{
    int n;        //n个点 
    TYPE * x;     //x,y为点的指针，首尾必须重合 
    TYPE * y;
    POLY() : n(0), x(NULL), y(NULL) {};
    POLY(int _n_, const TYPE * _x_, const TYPE * _y_)
    {     
        n = _n_;
        x = new TYPE[n + 1];
        memcpy(x, _x_, n*sizeof(TYPE));
        x[n] = _x_[0];
		
        y = new TYPE[n + 1];
        memcpy(y, _y_, n*sizeof(TYPE));
        y[n] = _y_[0];
    }
};

TYPE Cross(const POINT & a, const POINT & b, const POINT & o)
{return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}

// planar points' distance
//  两个点的距离 
TYPE Distance(const POINT & a, const POINT & b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));}


// 点阵的凸包，返回一个多边形 
POLY ConvexHull(const POINT * set, int n)            // 不适用于点少于三个的情况
{
    POINT * points = new POINT[n];
    memcpy(points, set, n * sizeof(POINT));
	
    TYPE * X = new TYPE[n];
    TYPE * Y = new TYPE[n];
	
    int i, j, k = 0, top = 2;
    for(i = 1; i < n; i++)
    {
        if ((points[i].y < points[k].y) ||
            ((points[i].y == points[k].y) &&
            (points[i].x < points[k].x)))
        {
            k = i;
        }
    }
	
    std::swap(points[0], points[k]);
	
    for (i = 1; i < n - 1; i++)
    {
        k = i;
        for (j = i + 1; j < n; j++)
        {
            if ((Cross(points[j], points[k], points[0]) > 0) ||
                ((Cross(points[j], points[k], points[0]) == 0) &&
                (Distance(points[0], points[j]) < Distance(points[0], points[k]))))
            {
                k = j;
            }
        }
        std::swap(points[i], points[k]);
    }
	
    X[0] = points[0].x; Y[0] = points[0].y;
    X[1] = points[1].x; Y[1] = points[1].y;
    X[2] = points[2].x; Y[2] = points[2].y;
	
    for (i = 3; i < n; i++)
    {
        while (Cross(points[i], POINT(X[top], Y[top]), 
            POINT(X[top - 1], Y[top - 1])) >= 0)
        {
            top--;
        }
        ++top;
        X[top] = points[i].x;
        Y[top] = points[i].y;
    }
	
    delete [] points;
    POLY poly(++top, X, Y);
    delete [] X;
    delete [] Y;
    return poly;
}


int main()
{
	POLY tubao;
	POINT ps[1100];
	int n,l,t;
	double len;
	scanf("%d",&t);
	while(t--) {
		scanf("%d %d",&n,&l);
		for (int i=0;i<n;i++) {
			scanf("%lf %lf",&ps[i].x,&ps[i].y);
		}
		tubao = ConvexHull(ps,n);
		len = 0;
		for (i=1;i<=tubao.n;i++) {
			len += Distance(POINT(tubao.x[i], tubao.y[i]), POINT(tubao.x[i-1], tubao.y[i-1]));
		}
		printf("%.0lf\n",2*Pi*l + len);
		if(t>0)	printf("\n");
	}
}