2361.cpp

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

/* This Code is Submitted by wywcgs for Problem 2361 on 2007-01-25 at 17:12:07 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 160;

class Point {
public:
	double x, y;
	void make() { scanf("%lf %lf", &x, &y); }
	double dis(const Point& p) const { return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y); }
	bool operator <(const Point&) const;
};
Point bs;
bool Point::operator <(const Point& p) const {
	double x1 = x-bs.x, y1 = y-bs.y, x2 = p.x-bs.x, y2 = p.y-bs.y;
	return atan2(y1, x1)+1e-6 < atan2(y2, x2);
}

class Circle {
public:
	Point o;
	double R;
	void make(int r) { o.make(); R = (double)r; }
	bool inter(const Point&, const Point&) const;
};
bool Circle::inter(const Point& a, const Point& b) const {
	double A = b.y-a.y, B = a.x-b.x, V = A*(o.x-a.x)+B*(o.y-a.y);
	if(V*V > R*R*(A*A+B*B)) return false;
	if(o.dis(a) <= R*R || o.dis(b) <= R*R) return true;
	double x0 = b.y-a.y, y0 = a.x-b.x, x1 = a.x-o.x, y1 = a.y-o.y, x2 = b.x-o.x, y2 = b.y-o.y;
	double va = x0*y1-x1*y0, vb = x0*y2-x2*y0;
	return (va > 0 && vb < 0) || (va < 0 && vb > 0);
}

bool rope[N][N];
Point p[N];
Circle c[N];
int opt[N][N], n;

int find(int, int);

int main()
{
	int g, r;
	
	while(scanf("%d %d %d", &n, &g, &r) != EOF) {
		for(int i = 0; i < n; i++) p[i].make();
		bs = p[0]; sort(p+1, p+n);
		for(int i = 0; i < g; i++) c[i].make(r);
		for(int i = 0; i < n; i++)
			for(int j = i+1; j < n; j++) {
				bool connect = true;
				if(j == (i+1)%n || i == (j+1)%n) connect = false;
				for(int k = 0; k < g && connect; k++)
					if(c[k].inter(p[i], p[j])) connect = false;
				rope[i][j] = rope[j][i] = connect;
			}
		memset(opt, -1, sizeof(opt));
		printf("%d\n", find(0, n-1));
	}
	
	return 0;
}

int find(int b, int e)
{
	if(opt[b][e] != -1) return opt[b][e];
	if((b+1)%n == e) return 0;
	opt[b][e] = 0;
	for(int i = (b+1)%n; i != e; i = (i+1)%n) {
		int k = 0;
		if(rope[i][b]) k++;
		if(rope[i][e]) k++;
		opt[b][e] >?= find(b, i)+find(i, e)+k;
	}
	return opt[b][e];
}