| ||||||||||
| 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