Codeforces 935C(计算几何)

Codeforces 938D
题意:给你一个圆心$(x_1,y_1)$和半径$r$。接着给你一个位置$(x_2,y_2)$,这个位置是不能覆盖的禁止点。现在有点,以点为中心,可以覆盖半径任意大,问在不覆盖禁止点前提下,将圆覆盖到最大,输出这个点覆盖最大的圆心和半径。

分类讨论:
1、这个点在圆外
显然可以覆盖整个圆,所以直接输出$(x_2,y_2)$和$r$
2、这个点在圆心上
显然覆盖点的半径为$r/2$,随便在圆内找一点即可。
3、这个点在圆内
圆内直径最长。设$A(x_1,y_1), C(x_2,y_2)$,考虑连接$AC$,再反向延长$AC$,与圆交于$F$, 则$CF/2$为覆盖点半径。求这个点的坐标可以根据$A,C$点与覆盖点构造相似三角形($A$型相似),求得$C$与覆盖点的$x,y$坐标差,即可得到覆盖点半径,对于覆盖点相对于$A$的位置,可以根据$x_1-x_2$和$y_1-y_2$的符号判断,具体看程序实现。

Codeforces Submission

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
db R, xx1, yy1, xx2, yy2;
db dist(db aa1, db bb1, db aa2, db bb2) {
return sqrt((aa1 - aa2) * (aa1 - aa2) + (bb1 - bb2) * (bb1 - bb2));
}
void clean() {
}
int solve() {
clean();
db d = dist(xx1, yy1, xx2, yy2);
if (d - R >= 0) return printf("%.10f %.10f %.10f\n", xx1, yy1, R), 0; //圆外
if (xx1 == xx2 && yy1 == yy2) return printf("%.10f %.10f %.10f\n", xx1 + R / 2, yy1, R / 2), 0; //圆心上
db r = (R + d) / 2;
db AE = xx2 - xx1;
db CE = yy2 - yy1;//覆盖点相对于A的位置(加减)由符号定
return printf("%.10f %.10f %.10f\n", xx2 - AE * r / d, yy2 - CE * r / d, r), 0; //圆内
}
int main() {
scanf("%lf%lf%lf%lf%lf", &R, &xx1, &yy1, &xx2, &yy2), solve();
return 0;
}

------ 本文结束 ------