本文共 1625 字，大约阅读时间需要 5 分钟。
刷一发凸包模板。
这个题， 我们可以发现， 凹进去的是没有用的... 所以答案就是点构成的凸包的周长+一个圆的周长。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define pb(x) push_back(x)#define ll long long#define mk(x, y) make_pair(x, y)#define lson l, m, rt<<1#define mem(a) memset(a, 0, sizeof(a))#define rson m+1, r, rt<<1|1#define mem1(a) memset(a, -1, sizeof(a))#define mem2(a) memset(a, 0x3f, sizeof(a))#define rep(i, n, a) for(int i = a; i pll;const double PI = acos(-1.0);const double eps = 1e-8;const int mod = 1e9+7;const int inf = 1061109567;const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };const int maxn = 1005;struct point{ int x,y;};point a[maxn];int st[maxn], top;int cross(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 p1,point p2){ return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));}bool cmp(point p1,point p2){ int tmp=cross(a[0],p1,p2); if(tmp>0) return true; else if(tmp==0&&dis(a[0],p1) a[i].y) || ((p0.y==a[i].y)&&(p0.x>a[i].x)) ) { p0.x=a[i].x; p0.y=a[i].y; k=i; } } a[k]=a[0]; a[0]=p0; sort(a+1,a+n,cmp);}void graham(int n){ int i; if(n==1) {top=0;st[0]=0;} if(n==2) { top=1; st[0]=0; st[1]=1; } if(n>2) { for(i=0;i<=1;i++) st[i]=i; top=1; for(i=2;i 0&&cross(a[st[top-1]],a[st[top]],a[i])<=0) top--; top++; st[top]=i; } }}int main(){ int n, r; while(cin>>n>>r) { init(n); graham(n); double ans = 0; for(int i = 0; i
转载于:https://www.cnblogs.com/yohaha/p/5257921.html