http://poj.org/problem?id=1379
Run Away
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 6095 | Accepted: 1869 |
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).题意：给出一个矩形的范围和其中的n个点，问，在这个矩形内距离这n个点的最近距离最远的坐标是多少；
分析：首先在<X,Y>范围内随机出op个可能的局部最优解，然后对于每个随机出来的点在进行任意方向的扩展（利用随机弧度实现）；
#include"string.h"
#include"stdio.h"
#include"queue"
#include"stack"
#include"vector"
#include"algorithm"
#include"iostream"
#include"math.h"
#include"stdlib.h"
#define M 1010
#define inf 100000000000
#define eps 1e-10
#define PI acos(-1.0)
using namespace std;
struct node
{
double x,y,dis;
}p[M],q[50],d[50];
double X,Y;
int n;
double min(double a,double b)
{
return a<b?a:b;
}
double max(double a,double b)
{
return a>b?a:b;
}
double pow(double x)
{
return x*x;
}
double len(double x1,double y1,double x2,double y2)
{
return pow(x1-x2)+pow(y1-y2);
}
double fun(double x,double y)
{
double mini=inf;
for(int i=1;i<=n;i++)
{
double L=len(x,y,p[i].x,p[i].y);
if(mini>L)
mini=L;
}
return mini;
}
void solve()
{
int po=15,est=25,i,j;
for(i=1;i<=po;i++)
{
q[i].x=(rand()%1000+1)/1000.0*X;
q[i].y=(rand()%1000+1)/1000.0*Y;
q[i].dis=fun(q[i].x,q[i].y);
}
double temp=sqrt(X*X+Y*Y);
double rate=0.9;
while(temp>eps)
{
for(i=1;i<=po;i++)
{
for(j=1;j<=est;j++)
{
double rad=(rand()%1000+1)/1000.0*PI*10;
node now;
now.x=q[i].x+temp*cos(rad);
now.y=q[i].y+temp*sin(rad);
if(now.x<0||now.x>X||now.y<0||now.y>Y)continue;
now.dis=fun(now.x,now.y);
if(now.dis>q[i].dis)
q[i]=now;
}
}
temp*=rate;
}
int indx=1;
for(i=1;i<=po;i++)
{
if(q[i].dis>q[indx].dis)
indx=i;
}
printf("The safest point is (%.1lf, %.1lf).
",q[indx].x,q[indx].y);
}
int main()
{
int T,i;
cin>>T;
while(T--)
{
scanf("%lf%lf%d",&X,&Y,&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
}
}