D.Mutikill
给定圆半径长,求最多可覆盖平面上多少点。
定长圆覆盖问题,和poj 1981可说是一模一样。
然后僵尸可能一个都木有(所以这题一定是搞计算几何的人来坑搞计算几何的了,或者是我太碍板了= =。。)
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; #define LL long long #define MAXN 310 #define eps 1e-10 const double pi = acos(-1.0); int sig(double x) { return (x > eps) - (x < -eps); } typedef struct Point { double x, y; Point() {} Point(double _x, double _y): x(_x), y(_y) {} bool operator <(const Point &argu) const { if(sig(x - argu.x) == 0) return y < argu.y; return x < argu.x; } double dis(const Point &argu) const { return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y)); } double dis2(const Point &argu) const { return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y); } double operator ^(const Point &argu) const { return x * argu.y - y * argu.x; } double operator *(const Point &argu) const { return x * argu.x + y * argu.y; } Point operator -(const Point &argu) const { return Point(x - argu.x, y - argu.y); } double len2() const { return x * x + y * y; } double len() const { return sqrt(x * x + y * y); } void in() { scanf("%lf%lf", &x, &y); } void out() { printf("%.10lf %.10lf\n", x, y); } }Vector; struct Arc { double ang; int in; bool operator <(const Arc &argu) const { return sig(ang - argu.ang) ? (ang < argu.ang) : (in > argu.in); } }arc[MAXN]; int n; double r; Point p[MAXN]; int max(int a, int b) { return a > b ? a : b; } int MAX_CirCle_Cover(double r) { int ret = 0; for(int i = 0; i < n; i++) { int cnt = 0; for(int j = 0; j < n; j++) { if(i == j) continue; double d = p[i].dis(p[j]); if(sig(d - 2.0 * r) > 0) continue; double theta = atan2(p[i].y - p[j].y, p[i].x - p[j].x); if(theta < 0) theta += 2 * pi; double phi = acos(d / (2.0 * r)); arc[cnt].ang = theta - phi + 2 * pi; arc[cnt++].in = 1; arc[cnt].ang = theta + phi + 2 * pi; arc[cnt++].in = 0; } sort(arc, arc + cnt); int tmp = 0; for(int i = 0; i < cnt; i++) { if(arc[i].in) tmp++; else tmp--; ret = max(ret, tmp); } } return ret + 1; } int work() { scanf("%lf%d", &r, &n); if(sig(r) == 0 || n == 0) return 0; for(int i = 0; i < n; i++) p[i].in(); return MAX_CirCle_Cover(r); } int main() { // freopen("D_std.in", "r", stdin); int c; scanf("%d", &c); while(c--) { printf("%d\n", work()); } return 0; }