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