| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我在网上找的数据都过了。。为什么这里还是WA。。望神犇指导。。#include <cstdio>
#include <cmath>
#define inf 2147483647
const double pi=3.141592653589793238462643383279502884197169399375105820974944;
struct POINT
{
int x,y;
double sita;
}a[1001];
int n,l,tb[1001],tot=0;
double dodo(int s,int t)
{
int x1,x2,y1,y2;
x1=a[s].x;x2=a[t].x;y1=a[s].y;y2=a[t].y;
return double((x2-x1)/sqrt(double((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))));
}
void qsort(int l,int r)
{
int i,j;
double mid;
POINT tmp;
i=l;j=r;mid=a[(l+r)>>1].sita;
do
{
while (a[i].sita<mid) ++i;
while (a[j].sita>mid) --j;
if (i<=j)
{
tmp=a[i];a[i]=a[j];a[j]=tmp;
++i;--j;
}
}while (i<=j);
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
void init()
{
int i,tmpx=inf,tmpy=inf,tmpd;
scanf("%d%d\n",&n,&l);
for (i=1;i<=n;i++) scanf("%d%d\n",&a[i].x,&a[i].y);
for (i=1;i<=n;i++)
if (a[i].y<tmpy){tmpy=a[i].y;tmpd=i;} else if (a[i].y==tmpy&&a[i].x<tmpx){tmpx=a[i].x;tmpd=i;}
a[tmpd].sita=double(-1);
for (i=1;i<=n;i++) if (i!=tmpd) a[i].sita=dodo(tmpd,i);
qsort(1,n);
}
int chacheng(int d1,int d2,int d3)
{
int x1,x2,x3,y1,y2,y3;
x1=a[d1].x;x2=a[d2].x;x3=a[d3].x;
y1=a[d1].y;y2=a[d2].y;y3=a[d3].y;
return ((x2-x3)*(y1-y2)-(y2-y3)*(x1-x2));
}
double dis(int i,int j)
{
return sqrt(double((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)));
}
void work()
{
int i;
double ans=0;
tb[1]=1;tb[2]=2;tb[3]=3;tot=3;
for (i=4;i<=n;i++)
{
while ((tot>=3)&&(chacheng(i,tb[tot],tb[tot-1])>0))
--tot;
++tot;tb[tot]=i;
}
ans+=dis(tb[tot],tb[1])+2*pi*l;
for (i=2;i<=tot;i++) ans+=dis(tb[i-1],tb[i]);
printf("%d",(int)(ans+0.5));
}
int main()
{
init();
work();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator