2140.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2140 on 2006-04-09 at 17:23:12 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int EM = 1024;
const double eps = 1e-8;

inline double form(double x) { return fmod(x+2*M_PI, 2*M_PI); }

class Edge {
public:
	double ag;
	int o, leave;
	void set(int, double, int);
	bool operator <(const Edge&) const;
};
void Edge::set(int cl, double ca, int co) {
	leave = cl; ag = form(ca); o = co;
}
bool Edge::operator <(const Edge& e) const {
	if(fabs(ag-e.ag) > eps) return ag < e.ag;
	else return leave < e.leave;
}

int main()
{
	Edge edge[EM];
	bool vst[EM];
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n, d, en = 0; scanf("%d %d", &n, &d);
		fprintf(stderr, "%d : %d %d\n", t+1, n, d);
		for(i = 0; i < n; i++) {
			int x, y; scanf("%d %d", &x, &y);
			if(x*x+y*y <= d*d) continue;
			double base = atan2(1.0*y, 1.0*x), ex = asin(d/sqrt(1.0*x*x+y*y));
			edge[en++].set(0, base-ex, i);
			edge[en++].set(1, base+ex, i);
		}
		sort(edge, edge+en); int best = en;
		for(i = 0; i < en; i++) {
			if(edge[i].leave) continue;
			memset(vst, false, sizeof(vst));
			int used = 0, cn = 0, cq[EM];
			for(j = 0; j < en; j++) {
				int o = (i+j) % en;
				if(!edge[o].leave) vst[edge[o].o] = true, cq[cn++] = edge[o].o;
				else if(vst[edge[o].o]) {
					used++;
					while(cn != 0) vst[cq[--cn]] = false;
				}
			}
			used += cn;
			best = min(best, used);
		}
		printf("%d\n", best);
	}

	return 0;
}