HDU 1109

http://acm.hdu.edu.cn/showproblem.php?pid=1109

一个范围内给一堆点,求到这些点的最短距离最大

模拟退火,温度是步长

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <ctime>
#include <cmath>
using namespace std ;
const double eps=1e-18 ;
int X,Y,M ;

struct point
{
    double x,y ;
    int OK()
    {
        if(x>-eps && x<X+eps && y>-eps && y<Y+eps)return 1 ;
        return 0 ;
    }
}p[1005],r[50] ;

double dis(point a,point b)
{
    return sqrt(pow(a.x-b.x,2)+pow(b.y-a.y,2)) ;
}

double ans[55] ;

int main()
{
    int T ;
    scanf("%d",&T) ;
    srand(time(NULL)) ;
    while(T--)
    {
        scanf("%d%d%d",&X,&Y,&M) ;
        for(int i=0 ;i<M ;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y) ;
        }
        for(int i=0 ;i<50 ;i++)
        {
            r[i].x=(rand()%1000+1)/1000.0*X ;
            r[i].y=(rand()%1000+1)/1000.0*Y ;
            ans[i]=1e18 ;
            for(int j=0 ;j<M ;j++)
            {
                ans[i]=min(ans[i],dis(p[j],r[i])) ;
            }
        }
        double tmp=max(X,Y) ;
        while(tmp>0.01)
        {
            for(int i=0 ;i<50 ;i++)
            {
                point now=r[i],next ;
                for(int j=0 ;j<50 ;j++)
                {
                    double rad=(rand()%1000+1)/1000.0*2*3.1415926535 ;
                    next.x=now.x+cos(rad)*tmp ;
                    next.y=now.y+sin(rad)*tmp ;
                    if(!next.OK())continue ;
                    double m=1e18 ;
                    for(int k=0 ;k<M ;k++)
                        m=min(m,dis(p[k],next)) ;
                    if(m>ans[i])
                    {
                        ans[i]=m ;
                        r[i]=next ;
                    }
                }
            }
            tmp*=0.8 ;
        }
        double res=0.0 ;
        int idx ;
        for(int i=0 ;i<50 ;i++)
        {
            if(ans[i]>res)
            {
                res=ans[i] ;
                idx=i ;
            }
        }
        printf("The safest point is (%.1lf, %.1lf).\n",r[idx].x,r[idx].y) ;
    }
    return 0 ;
}

时间: 10-16

HDU 1109的相关文章

(hdu step 1.3.8)Who&#39;s in the Middle(排序)

题目: Who's in the Middle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2938 Accepted Submission(s): 1109   Problem Description FJ is surveying his herd to find the most average cow. He wants to k

转载:hdu 题目分类 (侵删)

转载:from http://blog.csdn.net/qq_28236309/article/details/47818349 基础题:1000.1001.1004.1005.1008.1012.1013.1014.1017.1019.1021.1028.1029. 1032.1037.1040.1048.1056.1058.1061.1070.1076.1089.1090.1091.1092.1093. 1094.1095.1096.1097.1098.1106.1108.1157.116

HDU 6203 ping ping ping [LCA,贪心,DFS序,BIT(树状数组)]

题目链接:[http://acm.hdu.edu.cn/showproblem.php?pid=6203] 题意 :给出一棵树,如果(a,b)路径上有坏点,那么(a,b)之间不联通,给出一些不联通的点对,然后判断最少有多少个坏点. 题解 :求每个点对的LCA,然后根据LCA的深度排序.从LCA最深的点对开始,如果a或者b点已经有点被标记了,那么continue,否者标记(a,b)LCA的子树每个顶点加1. #include<Bits/stdc++.h> using namespace std;

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

hdu 1207 汉诺塔II (DP+递推)

汉诺塔II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4529    Accepted Submission(s): 2231 Problem Description 经典的汉诺塔问题经常作为一个递归的经典例题存在.可能有人并不知道汉诺塔问题的典故.汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往

[hdu 2102]bfs+注意INF

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 感觉这个题非常水,结果一直WA,最后发现居然是0x3f3f3f3f不够大导致的--把INF改成INF+INF就过了. #include<bits/stdc++.h> using namespace std; bool vis[2][15][15]; char s[2][15][15]; const int INF=0x3f3f3f3f; const int fx[]={0,0,1,-1};

HDU 3555 Bomb (数位DP)

数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数,它是按位来进行计数统计的,可以保存子状态,速度较快.数位dp做多了后,套路基本上都差不多,关键把要保存的状态给抽象出来,保存下来. 简介: 顾名思义,所谓的数位DP就是按照数字的个,十,百,千--位数进行的DP.数位DP的题目有着非常明显的性质: 询问[l,r]的区间内,有多少的数字满足某个性质 做法根据前缀和的思想,求出[0,l-1]和[0,r]中满足性质的数的个数,然后相减即可. 算法核心: 关于数位DP,貌似写法还是

HDU 5917 Instability ramsey定理

http://acm.hdu.edu.cn/showproblem.php?pid=5917 即世界上任意6个人中,总有3个人相互认识,或互相皆不认识. 所以子集 >= 6的一定是合法的. 然后总的子集数目是2^n,减去不合法的,暴力枚举即可. 选了1个肯定不合法,2个也是,3个的话C(n, 3)枚举判断,C(n, 4), C(n, 5) #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using name

hdu 6166 Senior Pan

地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6166 题目: Senior Pan Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 245    Accepted Submission(s): 71 Problem Description Senior Pan fails i