http://acm.pku.edu.cn/JudgeOnline/problem?id=1136

Код:
#include <stdio.h>
#include <math.h>

#define MAX_HOOKS 500
#undef DEBUG /* define DEBUG to get some on info on the pendulums path */
             /* this is highly advised when adding new test data       */

typedef struct { double x,y; } hook;

hook h[MAX_HOOKS]; /* position of hooks */
int n;             /* number of hooks */
double r;          /* length of pendulum */

int caseno = 1;

const double pi = 3.1415926535897932384626;
const double eps = 1e-8;

double dist(hook t1, hook t2)
{
  return sqrt((t1.x-t2.x)*(t1.x-t2.x) + (t1.y-t2.y)*(t1.y-t2.y));
}

double theta(hook h1, hook h2)
{
  double a;

  a = atan2(h2.y-h1.y,h2.x-h1.x);
  if(a < 0.0) a += 2.0*pi;
  return a*180.0/pi;
}

void solve_case()
{
  double l,a,angle,minangle,pendlen;
  hook center;
  int i,nxt;

  printf("Pendulum #%d\n",caseno++);

  /* simulation the pendulums swinging until it will touch no more hook */
  /* this is modification of a convex hull algorithm */

  /* 'center' holds the position around which the pendulum is currently
              swinging */
  center.x = center.y = 0.0;
  /* 'pendlen' is the length of the string from 'center' to the pendulums
               body */
  pendlen = r;

  /* 'l' is the traveled distance so far */
  l = 0.0;
  minangle = 180.0;
  do
    {
      /* This should not happen with correct input data! */
      if(pendlen < eps)
	fprintf(stderr,"ERROR: Pendulum hits hook!\n");

      nxt = -1; angle = minangle + 361.0;
      for(i=0;i<n;i++)
	if((h[i].x != center.x || h[i].y != center.y) 
	   && dist(center,h[i]) <= pendlen)
	  {
	    a = theta(center,h[i]);
	    while(a < minangle) a += 360.0;
	    if(a < angle || (a == angle && (nxt == -1 ||
 dist(center,h[i]) > dist(center,h[nxt]))))
	      { nxt = i; angle = a; }
	  }
      /* The next hook is not valid, if the pendulum had to move above
	 the x-axis to reach it */
      if(((int)((angle-90.0)/360.0) > (int)((minangle-90.0)/360.0) &&
	  center.y + pendlen > eps) ||
	 center.y + pendlen*sin(pi*angle/180.0) > eps)
	nxt = -1;
      /* test for another error condition. In good test data this should
	 not happen! */
      if((int)((angle-90.0)/360.0) > (int)((minangle-90.0)/360.0) &&
	 center.y + pendlen >= 0.0 && center.y + pendlen <= eps)
	fprintf(stderr,"ERROR: pendulum reaches dead point!\n");
      if(nxt == -1) 
	/* the pendulum will not touch another hook: we're done */
	/* there are two cases that can happen */
	if(center.y + pendlen <= eps)
	  { 
	    /* Case 1: the pendulum will swing forever in a circle around
	       a single hook */
	    l = 2.0*pi*pendlen; 
#ifdef DEBUG
	    fprintf(stderr,"! Pendulum swings in a circle of radius %g around (%g,%g)\n",
    pendlen,center.x,center.y);
#endif
	  }
	else
	  { 
	    /* Case 2: the pendulum will reach the x-axis again and
	       swing then back to its starting position (-r,0) */
	    angle = asin(-center.y/pendlen)*180.0/pi;
	    while(floor((angle+270.0)/360.0) <= floor((minangle-90.0)/360.0))
	      angle += 360.0;
	    l += pi*pendlen*(angle-minangle)/180.0;
	    l *= 2.0; /* count both directions */
#ifdef DEBUG
	    fprintf(stderr,"! Pendulum reaches angle %g and returns to its starting point.\n",
    angle);
#endif
	  }
      else
	/* the pendulum bends at the next hook */
	{
	  /* add travelled distance to the length of the orbit 'l' */
	  l += pi*pendlen*(angle-minangle)/180.0;
	  pendlen -= dist(center,h[nxt]);
	  minangle = angle;
	  center = h[nxt];
#ifdef DEBUG
	  fprintf(stderr,"! Pendulum bends at (%g,%g), new radius = %g, angle = %g\n",
  center.x,center.y,pendlen,minangle);
#endif
	}
    }
  while(nxt >= 0);

  printf("Length of periodic orbit = %.2f\n",l);
  printf("\n");
}

void skip_line() { while(getc(inp) >= ' '); }

int read_case()
{
  int i;

  fscanf(inp,"%d %lf",&n,&r);
  if(r == 0.0) return 0;
  skip_line();
  for(i=0;i<n;i++)
    {
      fscanf(inp,"%lf %lf",&h[i].x,&h[i].y);
      skip_line();
      /* skip all hooks above the x-axis; they don't matter anyway */
      if(h[i].y >= 0.0) { i--; n--; }
    }
  return 1;
}

int main()
{
  inp = stdin;
  while(read_case()) solve_case();
  return 0;
}