poj 1113Wall

http://poj.org/problem?id=1113

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=;
const double pi=acos(-1.0); struct point
{
double x,y;
bool operator <(const point &a)const
{
return (x<a.x)||(x==a.x&&y<a.y);
}
}p[maxn],ch[maxn]; double sqr(double x)
{
return x*x;
} double det(point a,point b,point c)
{
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
} double dis(point a,point b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
} int convex_hull(point *p,int n,point *ch)
{
sort(p,p+n);
int m=;
for(int i=; i<n; i++)
{
while(m>&&det(ch[m-],ch[m-],p[i])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-; i>=; i--)
{
while(m>k&&det(ch[m-],ch[m-],p[i])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;
} double diss(point *ch,int n)
{
double sum=;
for(int i=; i<n; i++)
{
sum+=dis(ch[i],ch[i-]);
}
return sum;
}
int main()
{
int n,l;
scanf("%d%d",&n,&l);
for(int i=; i<n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
int cn=convex_hull(p,n,ch);
printf("%.lf\n",(diss(ch,cn+)+*pi*l));
return ;
}
上一篇:Android Studio 每次运行都会再下载一遍,修改


下一篇:【ARC072E】Alice in linear land DP