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