ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1185. Wall

why i got WA
Posted by coma 10 Jun 2003 12:07
first i find the convex polygon
the answer is equal to the length of the convex polygon and 2*pi*l

is it right?

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535

struct point
{
double x,y;
};

struct point p[1001];
int n;
double l;
double dis;

double mul(point p1,point p2,point p0)
{
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y));
}

double dist(point q,point p)
{
return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)));
}

void init()
{
int i,j;
//FILE *fp=fopen("input.in","r");
scanf("%d%lf",&n,&l);
for (i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
}

void work()
{
int i,j;
int s;
int next[1001];
for (i=0;i<n;i++)
next[i]=(i+1)%n;
s=1;
while (s==1)
{
s=0;
for (i=0;i<n;i++)
if (next[i]!=-1)
{
if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14)
{
s=1;
j=next[i];
next[i]=next[next[i]];
next[j]=-1;
}
}
}
dis=0;
for (i=0;i<n;i++)
if (next[i]!=-1)
dis=dis+dist(p[i],p[next[i]]);
dis=dis+2*PI*l;
printf("%.0lf\n",dis+0.5);
}

main()
{
init();
work();
return 0;
}
the problem is 1185
Posted by coma 10 Jun 2003 12:15
> first i find the convex polygon
> the answer is equal to the length of the convex polygon and 2*pi*l
>
> is it right?
>
>
> #include <stdio.h>
> #include <math.h>
>
> #define PI 3.1415926535
>
> struct point
> {
> double x,y;
> };
>
> struct point p[1001];
> int n;
> double l;
> double dis;
>
> double mul(point p1,point p2,point p0)
> {
> return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y));
> }
>
> double dist(point q,point p)
> {
> return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)));
> }
>
> void init()
> {
> int i,j;
> //FILE *fp=fopen("input.in","r");
> scanf("%d%lf",&n,&l);
> for (i=0;i<n;i++)
>  scanf("%lf%lf",&p[i].x,&p[i].y);
> }
>
>
> void work()
> {
> int i,j;
> int s;
> int next[1001];
> for (i=0;i<n;i++)
>  next[i]=(i+1)%n;
> s=1;
> while (s==1)
>  {
>  s=0;
>  for (i=0;i<n;i++)
>   if (next[i]!=-1)
>    {
>    if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14)
>     {
>     s=1;
>     j=next[i];
>     next[i]=next[next[i]];
>     next[j]=-1;
>     }
>    }
>   }
> dis=0;
> for (i=0;i<n;i++)
>  if (next[i]!=-1)
>   dis=dis+dist(p[i],p[next[i]]);
> dis=dis+2*PI*l;
> printf("%.0lf\n",dis+0.5);
> }
>
> main()
> {
> init();
> work();
> return 0;
> }
who can help me???i've got WA for mant times
Posted by coma 10 Jun 2003 12:18
> > first i find the convex polygon
> > the answer is equal to the length of the convex polygon and 2*pi*l
> >
> > is it right?
> >
> >
> > #include <stdio.h>
> > #include <math.h>
> >
> > #define PI 3.1415926535
> >
> > struct point
> > {
> > double x,y;
> > };
> >
> > struct point p[1001];
> > int n;
> > double l;
> > double dis;
> >
> > double mul(point p1,point p2,point p0)
> > {
> > return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y));
> > }
> >
> > double dist(point q,point p)
> > {
> > return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)));
> > }
> >
> > void init()
> > {
> > int i,j;
> > //FILE *fp=fopen("input.in","r");
> > scanf("%d%lf",&n,&l);
> > for (i=0;i<n;i++)
> >  scanf("%lf%lf",&p[i].x,&p[i].y);
> > }
> >
> >
> > void work()
> > {
> > int i,j;
> > int s;
> > int next[1001];
> > for (i=0;i<n;i++)
> >  next[i]=(i+1)%n;
> > s=1;
> > while (s==1)
> >  {
> >  s=0;
> >  for (i=0;i<n;i++)
> >   if (next[i]!=-1)
> >    {
> >    if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14)
> >     {
> >     s=1;
> >     j=next[i];
> >     next[i]=next[next[i]];
> >     next[j]=-1;
> >     }
> >    }
> >   }
> > dis=0;
> > for (i=0;i<n;i++)
> >  if (next[i]!=-1)
> >   dis=dis+dist(p[i],p[next[i]]);
> > dis=dis+2*PI*l;
> > printf("%.0lf\n",dis+0.5);
> > }
> >
> > main()
> > {
> > init();
> > work();
> > return 0;
> > }