盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 方法1
  4. 方法2
  5. 更新日志

CF 2C Commentator problem (几何, 模拟退火)

题目

源地址:http://codeforces.com/problemset/problem/2/C

题意

给定三个圆的圆心坐标$(x_i, y_i)$和半径$r_i$,求点使得在该点看三个圆的视角相同,如果有多个点,取视角最大的点。
数据范围:$-10^3{\leq}x_i, y_i{\leq}10^3, 1{\leq}r_i{\leq}10^3$

方法1

从某个点观察某个圆的视角为:$2asin\frac{r}{d}$,其中$r$为圆的半径,$d$为点到圆心的半径。
所以对于两个圆来说:
两者的半径相同,那么观察视角相同的点所形成的曲线为一条直线,即两圆心所在直线的垂直平分线。
两者的半径不同,那么曲线为圆。为什么为圆呢,将圆心所在的直线设为$x$轴,其中一个圆心为原点,然后设视角相同的点为$(x, y)$,根据前面提到的视角相同的条件列出方程,会发现$x^2, y^2$的系数相同且不为0。所以曲线为圆。
知道这个线索之后,接下来题目就容易了。(只是理论AC容易了好么..)
圆$1$,圆$2$的曲线和圆$2$,圆$3$的曲线的交点即是所求的点,如果有多个点,取视角最大的即可。
问题就是以下几个情况:

  • 两直线求交点
  • 直线和圆求交点
  • 圆和圆求交点
1
挖个坑,这个方法还没有AC

方法2

神奇的模拟退火!
模拟退火是一个随机算法,原理大致是:在某个局部解的周围随机的探测,如果有更优解,则更新。(这点和大多数贪心很相似)但与普通贪心不同的是,模拟退火有一个跳出局部解的机制,即会选择非最优解也进行进一步的探测。

先来一份CF上看到的题解,选取重心为最开始的探测点,然后上下左右四个方向进行探测。但该方法没有一般性。后面有较为一般性的模拟退火

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
#define sqr(x) (x) * (x)
typedef long long ll;
typedef unsigned long long ULL;
double x[3], y[3], r[3], g[3];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
double f(double ax, double ay) { //f函数是三个视角中两两差的平方和,用来衡量解的优劣
for (int i = 0; i < 3; i++)
g[i] = sqrt(sqr(x[i] - ax) + sqr(y[i] - ay)) / r[i];
double tmp = 0;
for (int i = 0; i < 3; i++)
tmp += sqr(g[i] - g[(i + 1) % 3]);
return tmp;
}
int main () {
double dt = 1, ax = 0, ay = 0;
for (int i = 0; i < 3; i++) {
scanf("%lf%lf%lf", x + i, y + i, r + i);
ax += x[i], ay += y[i];
}
ax /= 3, ay /= 3; //选择重心进行探测
while(dt > eps) {
int fg = -1;
double now = f(ax, ay);
for (int i = 0; i < 4; i++) { //从四个方向进行探测
double nxt = f(ax + dx[i] * dt, ay + dy[i] * dt);
if (nxt < now) now = nxt, fg = i;
}
if (fg == -1) dt *= 0.5; //如果四个方向都没有找到最优解,则减小步长
else ax += dx[fg] * dt, ay += dy[fg] * dt; //否则更新探测中心
}
if (f(ax, ay) < eps) printf("%.5lf %.5lf\n", ax, ay);
return 0;
}

上述的探测方式没有一般性,下面是较为一般性的探测方式。(ps 还没有写完)

1
我又来挖坑了==|

更新日志

  • 2014-11-7 AC