https://ac.nowcoder.com/acm/contest/7830/D有一个大圆和一个小圆，两者内切于原点，然后再大圆内小圆外有若干个点，现在让你找一个圆使其和小圆外切，大圆内切，并且最大化该圆覆盖的点数这种多个圆有相切关系的题，考虑圆的反演反演：一个反演点O，一个反演半径R，在O的同侧有两个点P和P’，若满足|OP||OP’|=R*R，则P和P’互为反演点不经过反演点的圆的反演仍然是一个圆经过反演点的圆的反演是一条直线点反演还是点
再考虑本题，以小圆和大圆的内切点即原点为反演点，反演半径任意，这样就变成了两条直线，而要找的圆在反演后就是相切于这两条直线的圆，点反演后仍为点对于每个点，仅当圆心的纵坐标处于一个区间内才能覆盖，全部求出后差分前缀和即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
using db = double;
using pdi = pair<db, int>;
const db eps = 1e-8;
int sgn(db x) { return (x<-eps ? -1 : x>eps); }
db sqr(db x) { return x*x; }
int n;
db R, r, invr;
struct P
{
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator * (const db k) { return P(k*x, k*y); }
}p[N];
void solve()
{
cin >> n >> R >> r;
invr = 2*R;
db xl = 0.5*sqr(invr)/R, xr = 0.5*sqr(invr)/r;
db O = (xl+xr)/2, Or = (xr-xl)/2;
vector<pdi> seg;
for(int i=1; i<=n; i++)
{
cin >> p[i].x >> p[i].y;
db d = sqrt(sqr(p[i].x) + sqr(p[i].y));
db dd = sqr(invr)/d;
p[i] = p[i]*(dd/d);
db t = fabs(O-p[i].x);
if(sgn(Or-t)<0) continue;
db delta = sqrt(sqr(Or)-sqr(t));
seg.push_back({p[i].y-delta, 1});
seg.push_back({p[i].y+delta+eps, -1});
}
sort(begin(seg), end(seg));
int ans = 0, cur = 0;
for(auto it : seg)
{
cur += it.second;
if(cur>ans) ans = cur;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _; cin >> _;
while(_--) solve();
return 0;
}
|