- #include#include#include#include < string.h > #include#include
- // # include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- const int M = 5e5 + 10;
- const int mod = 1e9 + 7;
- const double pi = acos( - 1.0);#define RG register#define ST static double X,
- Y;
- int n;
- struct pa {
- double x,
- y;
- double dis;
- pa() {}
- pa(double x, double y, double dis) : x(x),
- y(y),
- dis(dis) {}
- }
- a[M];
- namespace SA {
- const double eps = 1e-2,
- DEC = 0.9,
- ACCEPT_DEC = 0.5;
- const int N = 30,
- T = 30,
- RAD = 1000;
- inline double rand01() {
- return rand() % (RAD + 1) / (1.0 * RAD);
- }
- inline double getdist(double x, double y) {
- double ret = 1e18;
- for (int i = 1; i <= n; ++i) ret = min(ret, (x - a[i].x) * (x - a[i].x) + (y - a[i].y) * (y - a[i].y));
- return ret;
- }
- pa res[N + 5];
- inline pa main() {
- res[1] = pa(0, 0, getdist(0, 0));
- res[2] = pa(X, 0, getdist(X, 0));
- res[3] = pa(0, Y, getdist(0, Y));
- res[4] = pa(X, Y, getdist(X, Y));
- for (int i = 5; i <= N; ++i) {
- double x = rand01() * X;
- double y = rand01() * Y;
- res[i] = pa(x, y, getdist(x, y));
- }
- double temper = max(X, Y),
- accept = 0.6;
- while (temper > eps) {
- for (int i = 1; i <= N; ++i) {
- for (int j = 1; j <= T; ++j) {
- double theta = rand01() * 2 * pi;
- double xx = res[i].x + temper * cos(theta);
- double yy = res[i].y + temper * sin(theta);
- if (0 <= xx && xx <= X && 0 <= yy && yy <= Y) {
- pa t = pa(xx, yy, getdist(xx, yy));
- if (t.dis > res[i].dis) res[i] = t;
- else if (rand01() <= accept) res[i] = t;
- }
- }
- }
- temper *= DEC;
- accept *= ACCEPT_DEC;
- }
- pa ans;
- ans.dis = 0;
- for (int i = 1; i <= N; ++i) if (res[i].dis > ans.dis) ans = res[i];
- return ans;
- }
- }
- int main() {
- srand(19260817);
- int T;
- cin >> T;
- while (T--) {
- cin >> X >> Y >> n;
- for (int i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);
- pa ans = SA: :main();
- printf("The safest point is (%.1f, %.1f).\n", ans.x, ans.y);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2075425.html