### 狗狗40题搞完纪念 » 1023

1023.cpp

```#include <cmath>
#include <cstdio>

const double EPS = 1e-4;
const int MAXN = 512;

inline bool lt(double a, double b) {
return a < b - EPS;
}

inline bool gt(double a, double b) {
return a > b + EPS;
}

inline bool eq(double a, double b) {
return fabs(a - b) < EPS;
}

int main() {
int ri = 0, n, p, q;
bool flag;
double t, r, dr, tr, alpha, beta, gamma;
double x[MAXN], y[MAXN];

while (scanf("%d%lf", &n, &r) != EOF && r > 0) {
x[0] = y[0] = 0;
p = 0;
alpha = -M_PI;
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf", &x[i], &y[i]);
}

t = 0;
while (true) {
// printf("@%d: %lf %lf (%lf)\n", p, alpha, r, t);
q = -1;
for (int i = 1; i <= n; ++i) {
if (i == p) {
continue;
}
tr = hypot(y[i] - y[p], x[i] - x[p]);
gamma = atan2(y[i] - y[p], x[i] - x[p]);
if (!lt(tr, r)) {
continue;
}
flag = false;
if (q == -1) {
flag = true;	// !eq(gamma, alpha);
} else if (eq(gamma, beta)) {
flag = gt(tr, dr);
} else if (lt(gamma, alpha)) {
flag = lt(beta, alpha) && lt(gamma, beta);
} else if (gt(gamma, alpha)) {
flag = lt(beta, alpha) || lt(gamma, beta);
}
if (flag) {
q = i;
dr = tr;
beta = gamma;
}
}

// valid beta?
flag = false;
if (gt(y[p] + r, 0)) {	// y[q] < 0
gamma = asin(-y[p] / r);
// printf("-> %lf+%lf>0: %lf %lf %lf\n", y[p], r, alpha, beta, gamma);
if (q == -1 ||
(lt(alpha, gamma) && lt(gamma, beta)) ||
(gt(alpha, beta) && (gt(gamma, alpha) || lt(gamma, beta)))) {
q = -1;
beta = gamma;
flag = true;
}
}
if (q != -1 || flag) {
if (lt(alpha, beta)) {
t += r * (beta - alpha);
} else if (lt(beta, alpha)) {	// !!
t += r * (beta - alpha + 2 * M_PI);
} else {
// t += 0;
}
}
if (q != -1) {
p = q;
r -= dr;
alpha = beta;
continue;
}

printf("Pendulum #%d\nLength of periodic orbit = ", ++ri);
printf("%.2lf\n\n", flag ? 2 * t : 2 * M_PI * r);
break;
}
}

return 0;
}

// ONLY WA TEST CASE #27 @ 1st try
// 3 27.0
// 0 -12
// 3 -8
// 6 -4

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//368 	2010-07-06 13:12:03 	Accepted 	1023 	C++ 	0 	180 	anotherpeg 	Source
```