poj 1379 Run Away (模拟退火)

 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    }

 1}
 2int main()
 3{
 4#ifndef  ONLINE_JUDGE 
 5    freopen("code/in.txt","r",stdin);
 6#endif
 7    int T;
 8    cin>>T;
 9    while (T--)
10    {
11	scanf("%lf%lf%d",&X,&Y,&n);
12	for ( int i = 0 ;  i < n ; i++)
13	    scanf("%lf %lf",&p[i].x,&p[i].y);
14	Point ans;
15	solve(p,n,ans);

1    }
2#ifndef ONLINE_JUDGE  
3    fclose(stdin);
4#endif
5    return 0;
6}