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 |
Re:一般是你程序的问题, 贴个代码看看In Reply To:Re:一般是你程序的问题, 贴个代码看看 Posted by:dosxp at 2008-09-01 21:59:09 > 谢谢 > > #include <stdio.h> > #include <cmath> > #include <algorithm> > using namespace std; > > const int MAX=1010; > const double EPS=1e-7; > const double INF=1e250; > const double PI =acos(-1.0); > > struct PT > { > double x,y,ang; > }pt[MAX]; > > int N,L,ps,stk[MAX]; > > inline double dis(PT a,PT b) > { > return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); > } > int cmp(PT a,PT b) > { > return a.ang-b.ang>EPS; > } > double crossP(PT a,PT b,PT c)// abXac cross product > { > return (c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.y-a.y); > } > inline int sign(double a) > { > if(fabs(a)<EPS) > return 0; > return a>EPS?1:-1; > } > > > int main() > { > int t,leftest,tt; > scanf("%d%d",&N,&L); > for(t=0;t<N;t++) > scanf("%lf%lf",&pt[t].x,&pt[t].y); > double minx,miny; > minx=miny=INF; > > for(t=0;t<N;t++) > { > if(sign(pt[t].y-miny)==-1 || (sign(pt[t].y-miny)==0 && sign(pt[t].x-minx)==-1)) > { > miny=pt[t].y; > minx=pt[t].x; > leftest=t; > } > } > swap(pt[0],pt[leftest]); > for(t=1;t<N;t++) > pt[t].ang=(pt[t].x-pt[0].x)/dis(pt[0],pt[t]); > sort(pt+1,pt+N,cmp); > for(t=0;t<=2;t++) > stk[t]=t; > ps=2; > for(t=3;t<N;t++) > { > while(crossP(pt[stk[ps-1]],pt[stk[ps]],pt[t])<EPS){ > ps--; > } > > ps++; > stk[ps]=t; > } > double sum=0.0; > > > for(t=0;t<=ps;t++) > { > sum+=dis(pt[stk[t]],pt[stk[(t+1)%(ps+1)]]); > } > > > sum+=PI*L*2; > > printf("%.0lf\n",sum); > > return 0; > } > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator