POJ1379 地图中有N个陷阱，给出他们的坐标，求一个点，使得这个点到所有陷阱的最小距离最大。 随机搞，选几个候选集，然后类似模拟退火的步骤，缩小步长。

Run Away

Time Limit: 3000MS

Memory Limit: 65536K

Total Submissions: 6348

Accepted: 1951

Description

One of the traps we will encounter in the Pyramid is located in the Large Room. A lot of small holes are drilled into the floor. They look completely harmless at the first sight. But when activated, they start to throw out very hot java, uh … pardon, lava. Unfortunately, all known paths to the Center Room (where the Sarcophagus is) contain a trigger that activates the trap. The ACM were not able to avoid that. But they have carefully monitored the positions of all the holes. So it is important to find the place in the Large Room that has the maximal distance from all the holes. This place is the safest in the entire room and the archaeologist has to hide there.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing three integers X, Y, M separated by space. The numbers satisfy conditions: 1 <= X,Y <=10000, 1 <= M <= 1000. The numbers X and Yindicate the dimensions of the Large Room which has a rectangular shape. The number M stands for the number of holes. Then exactly M lines follow, each containing two integer numbers Ui and Vi (0 <= Ui <= X, 0 <= Vi <= Y) indicating the coordinates of one hole. There may be several holes at the same position.

Output

Print exactly one line for each test case. The line should contain the sentence “The safest point is (P, Q).” where P and Qare the coordinates of the point in the room that has the maximum distance from the nearest hole, rounded to the nearest number with exactly one digit after the decimal point (0.05 rounds up to 0.1).

Sample Input

3
1000 50 1
10 10
100 100 4
10 10
10 90
90 10
90 90
3000 3000 4
1200 85
63 2500
2700 2650
2990 100

Sample Output

The safest point is (1000.0, 50.0).
The safest point is (50.0, 50.0).
The safest point is (1433.0, 1669.8).

Source

Central Europe 1999

POJ上用C++交可过， 用G++的话，要把输出改为 %f   如果WA，多交几次可破。


/* ***
Author :kuangbin
Created Time :2014/10/4 21:49:13
File Name :E:\2014ACM\专题学习\计算几何\模拟退火\POJ1379.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 10100;
const double PI = acos(-1.0);
struct Point{
double x,y;
void input(){
scanf(“%lf%lf”,&x,&y);
}
double distance(Point b){
return sqrt((x-b.x)(x-b.x)+(y-b.y)(y-b.y));
}
}p[MAXN],tp;
double dist;
int n;
double calc(Point p0){
double ret = 1e20;
for(int i = 0;i < n;i++)
ret = min(ret,p[i].distance(p0));
return ret;
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
double X,Y;
scanf(“%d”,&T);
srand(time(NULL));
int P = 15, L = 30;
while(T–){
scanf(“%lf%lf%d”,&X,&Y,&n);
for(int i = 0;i < n;i++)p[i].input();
for(int i = 0;i < P;i++){
tp[i].x = (rand()%1000+1)/1000.0X;
tp[i].y = (rand()%1000+1)/1000.0
Y;
dist[i] = calc(tp[i]);
}
double step = sqrt(X*X + Y*Y)/2;
while(step > 1e-5){
for(int i = 0;i < P;i++){
Point cur, pre = tp[i];
for(int j = 0;j < L;j++){
double angle = (rand()%1000+1)/1000.0*2*PI;
cur.x = pre.x + cos(angle)step;
cur.y = pre.y + sin(angle)
step;
if(cur.x < 0 || cur.x > X || cur.y < 0 || cur.y > Y)continue;
double tmp = calc(cur);
if(tmp > dist[i]){
tp[i] = cur;
dist[i] = tmp;
}
}
}
step *= 0.8;
}
int id;
double ans = 0;
for(int i = 0;i < P;i++)
if(dist[i] > ans){
ans = dist[i];
id = i;
}
printf(“The safest point is (%.1lf, %.1lf).\n”,tp[id].x,tp[id].y);
}
return 0;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 433.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%