具体算法参考《浅谈随机化思想在几何问题中的应用》。
C++ 125ms Accept！
void solve()
{
    int p=10,l=25;
    double delta,epsilon=1e-2,k1,k2,n1,n2,an[11];
    delta=(double)max(x,y)/(sqrt(1.0*m));
    for (int r=1;r<=p;r++)
      {
        q[r][0]=double(rand()%1000+1)/1000.000*x;
        q[r][1]=double(rand()%1000+1)/1000.000*y;
        double max=oo;
        for (int i=1;i<=m;i++)
          {
            double tmp=dist(q[r][0],q[r][1],hole[i].xi,hole[i].yi);
            if (tmp<max) max=tmp;
          }
        an[r]=max;
      }
    while (delta>epsilon)
      {
      for (int r=1;r<=p;r++)
        {
          for (int i=1;i<=l;i++)
            {
              k1=double(rand()%1000+1)/1000.000*delta;
              k2=sqrt(delta*delta-k1*k1);
              if (rand()%2==1) k1*=-1;
              if (rand()%2==1) k2*=-1;
              n1=q[r][0]+k1;
              n2=q[r][1]+k2;
              if (n1<=x&&n2<=y&&n1>=0&&n2>=0)
                {
                  double max1=oo;
                  for (int j=1;j<=m;j++)
                    {
                      double tmp=dist(n1,n2,hole[j].xi,hole[j].yi);
                      if (tmp<max1) max1=tmp;
                    }
                  if (max1>an[r])
                    q[r][0]=n1,q[r][1]=n2,an[r]=max1;
                }
              else
                continue;
            }
        }
      delta*=0.8;
      }
    double max=-oo;
    int s1=0;
    for (int r=1;r<=p;r++)
      if (an[r]>max)
        max=an[r],s1=r;
    ans.xi=q[s1][0];
    ans.yi=q[s1][1];
}

• Re:不好调整啊 (1681) HeadacherMM 2010-01-21 10:59:28