poj 1379 Run Away (模拟退火)

题意：给出一个矩形区域的长宽，给出区域中若干点，问距离所有点的最近距离的最大值是多少。

思路：很容易想到模拟退火。

比赛的时候因为忘记判断矩形边界导致答案错得离谱2333

加上之后1A

代码实现

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月28日 星期一 19时10分47秒
  4File Name :code/poj/1379.cpp
  5 ************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <string>
 15#include <cmath>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26using namespace std;
 27const double eps = 1E-8;
 28const int dx4[4]={1,0,0,-1};
 29const int dy4[4]={0,-1,1,0};
 30const int inf = 0x3f3f3f3f;
 31#define INF 1e8
 32#define MAX 1e6
 33#define MAXN 1005
 34double X,Y;
 35int n;
 36struct Point {
 37    double x, y;
 38    double d;
 39    Point() {}
 40    Point(double _x, double _y) : x(_x), y(_y) {}
 41    Point operator +(const Point &p) const {
 42	return Point(x + p.x, y + p.y);
 43    }
 44    Point operator -(const Point &p) const {
 45	return Point(x - p.x, y - p.y);
 46    }
 47    Point operator *(double k) const {
 48	return Point(x * k, y * k);
 49    }
 50    bool ok ()
 51    {
 52	if (x<0||y<0||x>X||y>Y) return false;
 53	return true;
 54    }
 55} p[MAXN];
 56const Point d[4] = {Point(-1, 0), Point(0, -1), Point(1, 0), Point(0, 1)};
 57double dis(const Point &a, const Point &b) {
 58    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
 59}
 60void solve(const Point *p, int n, Point &ret) {
 61    int i, j;
 62    double x, cur, ans = 0;
 63    const double delta = 0.95;
 64    bool tag;
 65    Point nxt;
 66    for (ret = p[0], x = (X+Y)/10; x > eps; x *= delta) {
 67	for (tag = true; tag;) {
 68	    for (tag = (i = 0); i < 4; ++i) {
 69		nxt.x = ret.x + dx4[i] * x * X;
 70		nxt.y = ret.y + dy4[i] * x * Y;
 71		if (!nxt.ok()) continue;
 72		for (cur=inf, j = 0; j < n; ++j) cur = min(cur,dis(nxt,p[j]));
 73		if (cur > ans) {
 74		    ans = cur; ret = nxt; tag = true;
 75		    break;
 76		}
 77	    }
 78	}
 79    }
 80
 81}
 82int main()
 83{
 84#ifndef  ONLINE_JUDGE
 85    freopen("code/in.txt","r",stdin);
 86#endif
 87    int T;
 88    cin>>T;
 89    while (T--)
 90    {
 91	scanf("%lf%lf%d",&X,&Y,&n);
 92	for ( int i = 0 ;  i < n ; i++)
 93	    scanf("%lf %lf",&p[i].x,&p[i].y);
 94	Point ans;
 95	solve(p,n,ans);
 96
 97	printf("The safest point is (%.1f, %.1f).\n",ans.x,ans.y);
 98
 99    }
100#ifndef ONLINE_JUDGE
101    fclose(stdin);
102#endif
103    return 0;
104}

相关文章