2493.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2493 on 2007-06-01 at 12:41:49 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 400;
const int PN = 24;

class Point {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
	int dis(const Point& p) const { return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y); }
};

Point p[PN];
double bg[N];
bool vst[N];

double rot(int, int, int, int);

int main()
{
	int n, r;
	
	while(scanf("%d %d", &r, &n) != EOF && r != -1) {
		for(int i = 0; i < n; i++) p[i].make();
		memset(vst, false, sizeof(vst));
		int m = n*n;
		for(int i = 0; i < m; i++) bg[i] = 1e200;
		for(int i = 1; i < n; i++) {
			int st = i, d = p[i].dis(p[0]);
			if(d > r*r) continue;
			bg[st] = rot(0, n-1, 0, i)+sqrt(1.0*d);
		}
		double rx = -1e20;
		for(int i = 0; i < m; i++) {
			double md = 1e200;
			int mi;
			for(int j = 0; j < m; j++)
				if(!vst[j] && md > bg[j]) { md = bg[j]; mi = j; }
			if(md > 1e100) break;
			vst[mi] = true;
			int bp = mi/n, ep = mi%n;
			if(ep == n-1) { rx = md; break; }
			for(int j = 0; j < n; j++) {
				int d = p[ep].dis(p[j]);
				if(d > r*r || j == ep) continue;
				bg[ep*n+j] <?= bg[mi]+sqrt(1.0*d)+rot(bp, ep, ep, j);
			}
		}
		if(rx < 0) printf("impossible\n");
		else printf("%.0lf\n", rx);
	}

	return 0;
}

double rot(int a, int b, int c, int d)
{
	double dx1 = p[b].x-p[a].x, dy1 = p[b].y-p[a].y;
	double dx2 = p[d].x-p[c].x, dy2 = p[d].y-p[c].y;
	double ag1 = atan2(dy1, dx1)*180/M_PI, ag2 = atan2(dy2, dx2)*180/M_PI;
	return min(fabs(ag1-ag2), 360-fabs(ag1-ag2));
}