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