1922.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1922
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define ABS(x) ((x)<0) ? -(x) : (x)
const int NMAX = 500 +10;
const double PI = acos(-1.0);
int n,d;
struct POINT {
	double arc;
	char pos;
	int idx;
	POINT() {}
	POINT(char a, double b, int c) : pos(a),idx(c) { 
		arc = fmod(b+2*PI,2*PI);
	}
	bool operator < (const POINT & pt) const {
		if (fabs(arc-pt.arc) > 1e-8) return arc < pt.arc;
		return pos < pt.pos;
	}
}ps[NMAX<<1];
int list[NMAX<<1];
int nlist;
bool flag[NMAX];
int nps;
int main() {
	int i,j,k,l,cas,ans;
	scanf("%d",&cas);
	while (cas --) {
		scanf("%d %d",&n,&d);
		for (nps=j=i=0;i<n;i++) {
			double x,y;
			scanf("%lf %lf",&x,&y);
			if (x*x+y*y-(1e-8) < d*d) continue;
			double org = atan2(y,x);
			double off = asin(d / sqrt(x*x+y*y));
			ps[nps++] = POINT('F',org-off,j);
			ps[nps++] = POINT('S',org+off,j++);
		}
		sort(ps,ps+nps);
		ans = nps>>1;
		for (i=0;i<nps;i++) {
			int cnt = 0;
			memset(flag,false,sizeof(flag));
			nlist = 0;
			for (k=0;k<nps;k++) {
				j = (i+k) % nps;
				if (ps[j].pos == 'F') {
					flag[ ps[j].idx ] = true;
					list[ nlist++ ] = ps[j].idx;
				}
				else if (flag[ ps[j].idx ]) {
					cnt ++;
					for (l=0;l<nlist;l++) flag[ list[l] ] = false;
					nlist = 0;
				}
			}
			ans = min(ans,cnt+nlist);
		}
		printf("%d\n",ans);
	}
}