生活就像一块巧克力,有时是WA型,有时是TLE型,你永远不知道你会得到哪一种

这道退火做的还是挺伤的..

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3644

感谢@JCarlson 翻译,题意摘自翻译:

所以我们设置R,表示到所有点/边的距离的最小值..

这时候就考验数学功底什么的了..

感谢@MengCl3 教我数学..

使用点积算出角度是否是钝角..钝角就算点到点的距离,不然算点到直线距离..

一直WA或者TLE..就像开头的那块巧克力..

后来发现..

卡常数是第一生产力..只有卡好常数..你才能多退几次..多退几次你才能AC..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{
    double x;
    double y;
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
    point (double xx=0,double yy=0)
    {
        x=xx;
        y=yy;
    }
    friend point operator - (const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend double operator * (const point &a,const point &b)
    {
        return a.x*b.y-a.y*b.x;
    }
    double dis(point &a)
    {
        return (x-a.x)*(x-a.x)+(y-a.y)*(y-a.y);
    }
    double distance_2(point &a,point &b)
    {
        double t=point(a.x-x,a.y-y)*point(b.x-x,b.y-y);
        return t*t/a.dis(b);
    }
    double multi_dot(point a)
    {
        return x*a.x+y*a.y;
    }
};
point a[55];
const double eps=1e-5;
int n;
double cross(point &a,point &b,point &c,point &d)
{
    if (((a-c)*(a-d))*((b-c)*(b-d))>=0) return false;
    if (((c-a)*(c-b))*((d-a)*(d-b))>=0) return false;
    return true;
}
double get_val(point &a,point &b,point &c)
{
    if ((a-b).multi_dot(c-b)<=0) return a.dis(b);
    if ((a-c).multi_dot(b-c)<=0) return a.dis(c);
    return a.distance_2(b,c);
}
bool try_best_ans(double expect_ans)
{
    double t=1e-6;
    double size=50;
    int temp=rand()%n;
    double x=a[temp].x;
    double y=a[temp].y;
    double cur_ans=0;
    for (;;)
    {
        if (size<1e-8) return false;
        double s=(double)rand()/RAND_MAX-0.5;
        double deltax=s*size*2;
        s=(double)rand()/RAND_MAX-0.5;
        double deltay=s*size*2;
        size*=0.99;
        double newx=x+deltax;
        double newy=y+deltay;
        point now_point=point(newx,newy);
        bool flag=0;
        int i;
        for (i=0;i<n;i++)
        {
            /*
            if (a[i].x==newx)
            {
                if (a[i+1].x<=newx) flag^=1;
                if (a[i+1].x!=newx) continue;
            }
            if (a[i+1].x==newx)
            {
                if (a[i].x<=newx) flag^=1;
                continue;
            }*/
            point t=point(newx,1e18);
            if (cross(now_point,t,a[i],a[i+1])) flag^=1;
        }
        if (flag==0) continue;
        double mins=1e18;
        for (i=0;i<n;i++)
        {
            mins=min(mins,get_val(now_point,a[i],a[i+1]));
        }
        if (mins+eps>=expect_ans)
        {
            return true;
        }
        if (mins>cur_ans)
        {
            cur_ans=mins;
            x=newx;
            y=newy;
        }
        else
        {
            if (exp((mins-cur_ans)/t)*RAND_MAX>rand())
            {
                cur_ans=mins;
                x=newx;
                y=newy;
            }
            t*=0.99;
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    srand(2011719);
    for (;;)
    {
        scanf("%d",&n);
        if (n==0) break;
        int i;
        for (i=0;i<n;i++)
        {
            a[i].read();
        }
        a[i]=a[0];
        double r;
        scanf("%lf",&r);
        for (i=0;i<30;i++)
        {
            if (try_best_ans(r*r))
            {
                puts("Yes");
                break;
            }
        }
        if (i==30)
        {
            puts("No");
        }
    }
    return 0;
}