Loading...

洛谷P2533[AHOI2012]信号塔

check评论:0 条 remove_red_eye浏览量:363 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-30

模拟退火题目

$Orz$随机增量法dalao 蒟蒻不会神仙方法,只能玩退火了

常规套路,每次随机步长,然后移动求值比较即可

因为我太菜了,所以直接用的$random\_shuffle$来随机了

#include <bits/stdc++.h>
#define twice(x) ((x)*(x)) 
using namespace std;
const int N=1e5+1;
const double eps=1e-7;
struct node
{
    double x,y;
}p[N],c;
int n;
double r;
double calc(const node &a,const node &b)
{
    return sqrt(twice(a.x-b.x)+twice(a.y-b.y));
}
node get_focus(const node &a,const node &b,const node &c)
{
    node t;
    double c1=(a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)/2.0;
    double c2=(c.x*c.x-b.x*b.x+c.y*c.y-b.y*b.y)/2.0;
    t.x=(c1*(c.y-b.y)-c2*(a.y-b.y))/((a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y));
    t.y=(c1*(c.x-b.x)-c2*(a.x-b.x))/((a.y-b.y)*(c.x-b.x)-(c.y-b.y)*(a.x-b.x));
    return t;
}
void work()
{
    random_shuffle(p+1,p+n+1);
    c=p[1];
    r=0;
    for(int i=2;i<=n;i++)
    {
        if(calc(p[i],c)+eps>r)
        {
            c=p[i];r=0;
            for(int j=1;j<i;j++)
            {
                if(calc(p[j],c)+eps>r)
                {
                    c.x=(p[i].x+p[j].x)/2;
                    c.y=(p[i].y+p[j].y)/2;
                    r=calc(c,p[j]);
                    for(int k=1;k<j;k++)
                    {
                        if(calc(p[k],c)+eps>r)
                        {
                            c=get_focus(p[i],p[j],p[k]);
                            r=calc(c,p[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.2lf %.2lf %.2lf ",c.x,c.y,r);
}
int main()
{
    srand(time(0));
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    work();
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名