Capture Stars
圆的反演
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
const int N = 1e4 + 10;
const double eps = 1e-6;
int T, n, R, r;
double x[N], y[N];
pdd seg[N];
inline void InvPoint(double &x, double &y) {
double d = x*x+y*y;
x = (4.0*R*R)/d*x;
y = (4.0*R*R)/d*y;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &n, &R, &r);
for (int i = 1; i <= n; ++i) scanf("%lf %lf", &x[i], &y[i]);
double fR = 2*R, fr = (4.0*R*R)/(2.0*r), m = (fR+fr)/2, mr = (fr-fR)/2;
for (int i = 1; i <= n; ++i) {
InvPoint(x[i], y[i]);
double dx = fabs(x[i]-m);
double dy = sqrt(mr*mr-dx*dx);
seg[i].fi = y[i]-dy;
seg[i].se = y[i]+dy;
}
sort(seg+1, seg+1+n);
priority_queue<double, vector<double>, greater<double> > q;
q.push(seg[1].se);
int ans = 1;
for (int i = 2; i <= n; ++i) {
while(!q.empty() && q.top() < seg[i].fi + eps) {
q.pop();
}
q.push(seg[i].se);
ans = max(ans, (int)q.size());
}
printf("%d\n", ans);
}
return 0;
}