Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:一般是你程序的问题, 贴个代码看看

Posted by feiadang at 2009-03-19 21:41:02 on Problem 1113
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator