首页 > 代码库 > poj 1379 Run Away 模拟退火 难度:1
poj 1379 Run Away 模拟退火 难度:1
Run Away
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 6482 | Accepted: 1993 |
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
31000 50 110 10100 100 410 1010 9090 1090 903000 3000 41200 8563 25002700 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).
思路:直接按照题解做的,首先列举30个随机点,然后分别进行短距离的随机尝试
#include <cstdio>#include <ctime>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;const double Pi=acos(-1.0);const double eps=1e-3;const double inf=1e20;double px[31],py[31],d[31],x[1111],y[1111];double caldis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int main(){ int T; scanf("%d",&T); srand(9876543); while(T--){ int a,b,m; scanf("%d%d%d",&a,&b,&m); for(int i=0;i<m;i++){ scanf("%lf%lf",x+i,y+i); } for(int i=0;i<30;i++){ px[i]=(double)(rand()%1000+1)/1000.000*a; py[i]=(double)(rand()%1000+1)/1000.000*b; d[i]=inf; for(int j=0;j<m;j++)d[i]=min(d[i],caldis(px[i],py[i],x[j],y[j])); } double delta=double(max(a,b))/(sqrt(1.0*m)); while(delta>eps){ for(int i=0;i<30;i++){ double tx=px[i],ty=py[i]; for(int j=0;j<30;j++){ double theta=(double)(rand()%1000+1)/1000.000*10*Pi; double dx=delta*cos(theta); double dy=delta*sin(theta); tx+=dx;ty+=dy; if(tx<0||tx>a||ty<0||ty>b){tx-=dx;ty-=dy;continue;} double td=inf; for(int k=0;k<m;k++)td=min(td,caldis(tx,ty,x[k],y[k])); if(td>d[i]){ d[i]=td;px[i]=tx;py[i]=ty; } tx-=dx;ty-=dy; } } delta*=0.9; } double ans=0;int ind=0; for(int i=0;i<30;i++){ if(d[i]>ans){ ind=i; ans=d[i]; } } printf("The safest point is (%.1f, %.1f).\n",px[ind],py[ind]); } return 0;}
poj 1379 Run Away 模拟退火 难度:1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。