欢迎大家访问我的老师的OJ———caioj.cn
题面描述
思路
简要题意大概就是:
给定n,l, 然后给定平面中n个点的横纵坐标,
求一个最小周长的封闭图形(可以包含曲线),
要求该图形包裹住所有点,
并且该封闭图形上的任何点距离任意给定点不小于l
输出这个最小周长
就以样例为例吧:
很明显,这个封闭图形的最小周长就为凸包周长加2πl。
AC code
此为Uva的提交
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define pi acos(-1.0)
using namespace std;
const int N=5e4+10;
struct node{double x,y;}p[N],h[N];
double mul(node p1,node p2,node p0)
{
double x1=p1.x-p0.x,y1=p1.y-p0.y;
double x2=p2.x-p0.x,y2=p2.y-p0.y;
return x1*y2-x2*y1;
}
bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
double dis(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int sta[N],tp,n;
bool used[N];
void tb()
{
sort(p+1,p+n+1,cmp);
tp=0;
sta[++tp]=1;
for(int i=2;i<=n;i++)//下凸壳
{
while(tp>1&&mul(p[sta[tp]],p[i],p[sta[tp-1]])<=0)used[sta[tp--]]=0;
used[i]=1;
sta[++tp]=i;
}
int top=tp;
for(int i=n-1;i;i--)//上凸壳
if(!used[i])
{
while(tp>top&&mul(p[sta[tp]],p[i],p[sta[tp-1]])<=0)used[sta[tp--]]=0;
sta[++tp]=i;
}
for(int i=1;i<=tp;i++)h[i]=p[sta[i]];
}
double calc()
{
double ans=0;
for(int i=2;i<=tp;i++)
ans+=dis(h[i-1],h[i]);
return ans;
}
int main()
{
int L;
int t;scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
tb();
double ans=calc()+2*pi*L;
printf("%d\n",(int)(ans+0.5));
if(t)puts("");
}
return 0;
}