poj 1379 Run Away (模拟退火)

poj 1379题目链接

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

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

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

加上之后1A

/* ***********************************************
Author :111qqz
Created Time :2016年08月28日 星期一 19时10分47秒
File Name :code/poj/1379.cpp
 ************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
#define INF 1e8
#define MAX 1e6
#define MAXN 1005
double X,Y;
int n;
struct Point {
    double x, y;
    double d;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    Point operator +(const Point &p) const {
	return Point(x + p.x, y + p.y);
    }
    Point operator -(const Point &p) const {
	return Point(x - p.x, y - p.y);
    }
    Point operator *(double k) const {
	return Point(x * k, y * k);
    }
    bool ok ()
    {
	if (x<0||y<0||x>X||y>Y) return false;
	return true;
    }
} p[MAXN];
const Point d[4] = {Point(-1, 0), Point(0, -1), Point(1, 0), Point(0, 1)};
double dis(const Point &a, const Point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void solve(const Point *p, int n, Point &ret) {
    int i, j;
    double x, cur, ans = 0;
    const double delta = 0.95;
    bool tag;
    Point nxt;
    for (ret = p[0], x = (X+Y)/10; x > eps; x *= delta) {
	for (tag = true; tag;) {
	    for (tag = (i = 0); i < 4; ++i) {
		nxt.x = ret.x + dx4[i] * x * X;
		nxt.y = ret.y + dy4[i] * x * Y;
		if (!nxt.ok()) continue;
		for (cur=inf, j = 0; j < n; ++j) cur = min(cur,dis(nxt,p[j]));
		if (cur > ans) {
		    ans = cur; ret = nxt; tag = true;
		    break;
		}
	    }
	}
    }
    
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    int T;
    cin>>T;
    while (T--)
    {
	scanf("%lf%lf%d",&X,&Y,&n);
	for ( int i = 0 ;  i < n ; i++)
	    scanf("%lf %lf",&p[i].x,&p[i].y);
	Point ans;
	solve(p,n,ans);

	printf("The safest point is (%.1f, %.1f).\n",ans.x,ans.y);

    }
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}