【FJOI2015】最小覆盖双圆问题

题目描述

给定平面上n个点(x_1,y_1),...,(x_n,y_n)(x1​,y1​),...,(xn​,yn​)，找出2个半径相同的圆R_1R1​和R_2R2​，覆盖给定的n个点，且半径最小。

设计一个算法，计算出所求最小覆盖双圆 R_1R1​ 和 R_2R2​ 的半径。

输入格式

输入有多个测试实例。每个实例的第1行中给出正整数n，n＜1000，表示平面上有n个点。

接下来的n行中每行给出2个实数(x, y)，-100000≤x≤100000，-100000≤y≤100000。

最后一行有一个0表示结束。

输出格式

对于每组数据，输出最小的符合题意的圆的半径，保留两位小数。

输入输出样例

输入 #1 3  0.00 0.00 1.00 0.00 0.00 4.00 10 0.00 0.00 0.00 3.00 1.00 6.00 2.00 2.00 3.00 5.00 5.00 3.00 6.00 3.00 9.00 5.00 10.00 5.00 11.00 3.00 0 输出 #1 0.50 3.05

说明/提示

对于100%的数据，n<=1000n<=1000，|x_i|,|y_i|<=100000∣xi​∣,∣yi​∣<=100000，（T<=10T<=10）

 

【题目大意】

n个点，现在给两个半径相同的圆去覆盖，求最小半径

【解题思路】

我们需要尽量可能的减少重复的点，即同时被两个圆覆盖的点

所以我们二分枚举这个中间点，让一个圆覆盖一部分

使点没有重复的被覆盖

一般情况下，我们直接按 x 排序二分

选择半径更大的一边，然后继续二分

但是这不行

因为这样实际上是用一根垂直于 x 轴的直线分两边的点

而这个直线可能会有一定斜率

 

所以这个中间点的查找就是一个问题

 

二分枚举中间的分界点，因为通过图可知

两个圆总会关于一条直线对称

两圆不相交时是一条，两圆相交时是他们的交线

我们需要一条直线将所有点分成两半

但是正像上面所说，是被交线分开的

所以两边的点并不会一定被这根线分成两半

于是我们枚举这根直线的斜率，同时为了更好的排序

我们直接旋转坐标系

旋转坐标系的过程参见线性代数

旋转这一步我觉得是这道题的关键，而其他题解都没有太说明

 

注意：

对于变量的使用，要注意之前他是否被变更过

调试代码的时候可以通过调整查看顺序达到更高的效率

（先看main ---> 顺序往下看）

 

#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> using namespace std; const int MAXN = 2*1e3 + 5 ; const double INF = 1e18 ; const double an = 1.0 / 180 * acos(-1); const double eps = 1e-9; const double si = sin(an), co = cos(an); int n; double reps() { return (1.0*rand() / RAND_MAX - 0.5)*eps; } struct V {double x, y;V() {}V(double a, double b) :x(a), y(b) {}V operator+(const V&b) const { return V(x + b.x , y + b.y);}V operator-(const V&b) const { return V(x - b.x , y - b.y);}bool operator<(const V&b) const { return x < b.x; }double operator*(const V&b) const { return x * b.y - y * b.x; }double operator^(const V&b) const { return x * b.x + y * b.y; }//叉乘V operator*(double b) const { return V(x * b , y*b); }V operator/(double b) const { return V(x / b , y /b); }void rota() { double x1 = x, y1 = y;x=x1 * co - y1 * si, y=x1 * si + y1 * co; }V rot() { return V(-y, x); }double len() { return (x*x + y * y); }}p[MAXN],o; typedef V P; struct L {V s, t;L(P a,P b):s(a),t(b){}friend P cross(L a, L b) { return a.s + a.t*(b.t*(b.s - a.s)) / (b.t*a.t); }//求交点 }; P circle(P a,P b, P c) {return cross(L((a + b)*0.5, (b - a).rot()), L((a + c)*0.5, (c - a).rot())); } //求圆心 P s[MAXN]; int sgn(double x) { return x<-eps ? -1 : x>eps; } double solve(int l,int r) {double r1;if (l > r) return 0;int cnt = 0;for (int i = l; i <= r; i++)s[++cnt] = p[i];random_shuffle(s + 1, s + 1 + cnt);r1 = 0, o = s[1];for (int i = 1; i <= cnt; i++){if (sgn((s[i] - o).len() - r1)>0){o = s[i], r1 = 0;for (int j = 1; j <= i - 1; j++)if (sgn((s[j] - o).len()-r1) > 0){o = (s[i] + s[j])*0.5, r1 = (s[j] - o).len();for (int k = 1; k <= j - 1; k++)if (sgn((s[k] - o).len() - r1)>0)o = circle(s[i], s[j], s[k]), r1 = (s[i] - o).len();}}}return r1; } int main() {srand(20030719);while (scanf("%d", &n) && n){for (int i = 1; i <= n; i++){scanf("%lf%lf", &p[i].x, &p[i].y);}double ans = INF;///double cnt = 180;for (int _ = 1; _ <= 181; _++){sort(p + 1, p + 1 + n);int l = 1, r = n;//printf("**\n");while (l <= r){int mid = (l + r) >> 1;double retl = solve(1, mid); double retr = solve(mid + 1, n);//printf("**\n");double tmp = max(retl, retr);//if (retr + retl - tmp > ans) break;ans = min(tmp, ans);if (retl > retr) r = mid - 1;else l = mid + 1;}for (int i = 1; i <= n; i++)p[i].rota();}printf("%.2lf\n", sqrt(ans));}return 0; } View Code

 

 

---

纪念我写完的第一道黑题

 

转载于:https://www.cnblogs.com/rentu/p/11347191.html

总结

以上是生活随笔为你收集整理的【FJOI2015】最小覆盖双圆问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。