# hihoCoder 1508-剑刃风暴

hihoCoder 1508-剑刃风暴

### 输出

10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7

3

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 2005;
const double PI = acos(-1.0);
//const double R = 1.0;//定义覆盖圆半径为R
int T, n, total, R;
struct Point {
double x, y;
}point[MAX_N];
struct Angle {
double data;
int is;
bool operator < (const Angle& rhs) const {
return data<rhs.data;
}
}angle[MAX_N * 2];
inline double Dis(Point a, Point b)//计算线段ab的长度
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
inline double God(Point a, Point b)//计算向量ab的极角
{
double res = atan(fabs((b.y - a.y) / (b.x - a.x)));
if (b.y<a.y) {
if (b.x<a.x) res += PI;
else res = 2 * PI - res;
}
else {
if (b.x<a.x) res = PI - res;
}
return res;
}
void solve()
{
int res = 1;
for (int i = 0; i<n; i++) {
total = 0;
for (int j = 0; j<n; j++) {
if (i == j) continue;
double dist = Dis(point[i], point[j]);
if (dist>2.0 * R) continue;
double base = God(point[i], point[j]);
double extra = acos((dist / 2.0) / R); //计算差角
angle[total].data = base - extra; // in
angle[total++].is = 1;
angle[total].data = base + extra; // out
angle[total++].is = -1;
}
if (total <= res) continue;
sort(angle, angle + total);
int tmp = 1;
for (int j = 0; j<total; j++) {
tmp += angle[j].is;
res = max(res, tmp);
}
}
printf("%d\n", res);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &R);
for (int i = 0; i<n; i++) {
scanf("%lf %lf", &point[i].x, &point[i].y);
}
solve();
return 0;
}