题目链接：点击打开链接
题意：给你n个顶点（代表城堡），要绕城堡外面建一个围墙，围住所有点，并且墙与所有点的距离至少为l，求这个墙最小的长度 。
思路：其实就是一个以l为半径的圆的circle+凸包周长。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #define PI acos(-1) using namespace std; const int maxn=1e3+10; struct Point//点 向量 { double x,y; Point(double x=0,double y=0):x(x),y(y) {} }; typedef Point Vector; //向量使用点作为表示方法 结构相同 为了代码清晰 const double eps = 1e-8; int dcmp(double x) //三态函数 处理与double零有关的精度问题 { if(fabs(x) < eps) return 0; return x<0 ? -1 : 1; } //向量运算 Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } bool operator == (const Vector& A, const Vector& B) { return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0; } bool operator < (const Point&a,const Point &b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } double Dot(Vector A, Vector B) //向量点积 { return A.x * B.x + A.y * B.y; } double Cross(Vector A, Vector B) //向量叉积 { return A.x * B.y - A.y * B.x; } double Dis(Point A, Point B)//两点距离 { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y)); } //求凸包 int ConvexHull(Point p[],int n,Point ch[]) { sort(p,p+n); int m = 0; for(int i = 0; i <n; i++) { while(m > 1 && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--; ch[m++] = p[i]; } int k = m; for(int i = n-2; i >= 0; i--) { while(m > k && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--; ch[m++] = p[i]; } if(n > 1) m--; return m; } //凸包周长 double PolygonCircle(Point *p, int n) { double circle = 0; p[n]=p[0]; for(int i=0; i<n; i++) circle+=Dis(p[i],p[i+1]); return circle; } int main() { Point p[maxn],ch[maxn]; int i,j,n,l,T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&l); for(i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); int m= ConvexHull(p,n,ch); printf("%.lf\n",(PolygonCircle(ch,m)+l*2*PI)); if(T)printf("\n"); } return 0; }
