Bakser's Blog

我是逗比。

bzoj3680 吊打GTY

| Comments

这题其实是经典问题了,我从奇怪的地方找到了几组数据,又自己加强了一坨数据就出上去了。
bzoj还把题目名给和谐了。。。。。原名是吊打GTY来着。

然后被搞的好惨。。。。。。
喜感的题目背景就是广义费马点问题的物理模拟方法,所以就是求广义费马点。
关于广义费马点可以看Matrix67的一篇文章
以下就是题解部分了

法一

广义费马点满足

用这个做估价然后启发式搜索,爬山法或模拟退火之类都可以,数据比较良心,可以过。
如果不了解广义费马点,我在数据范围里也给了提示,考虑一条直线上的情况,即邮局选址问题,经典的加权中位数问题。
加权中位数的那个约束式子和广义费马点是一样的,想一想也没什么道理不可推广,然后上就可以了。

我的naive的爬山法
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef double LD;
typedef unsigned long long LL;
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
template<class T>
inline void read(T &x)
{
    char c=0;bool flag(0);
    for(;c<'0'||c>'9';c=getchar())flag|=(c=='-');
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
    if(flag)x*=-1;
}
const int N(10200);
int n;
LD x[N],y[N],w[N];
inline LD dis(LD x,LD y,LD xx,LD yy)
{
    return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
inline LD calc(LD nx,LD ny)
{
    LD res(0);
    for(int i(1);i<=n;i++)
        res+=dis(nx,ny,x[i],y[i])*w[i];
    return res;
}
inline void dfs(LD rx,LD ry,LD val,LD r)
{
    if(r<0.0001)
    {
        printf("%.3lf %.3lf\n",rx,ry);
        exit(0);
    }
    LD dx,dy,ddx,ddy;
    LD tmp(val),tmp2;
    for(int i(1);i<=150;i++)
    {
        dx=(LD)1/LD(rand()%100)*(LD)r*(rand()&1?-1:1);
        LD len=sqrt(r*r-dx*dx);
        dy=(LD)1/LD(rand()%100)*(LD)(len)*(rand()&1?-1:1);
        tmp2=calc(rx+dx,ry+dy);
        if(tmp2<tmp)
        {
            ddx=dx;
            ddy=dy;
            tmp=tmp2;
        }
    }
    dfs(rx+ddx,ry+ddy,val,r/2);
}
int main()
{
    srand(10086);
    scanf("%d",&n);
    for(int i(1);i<=n;i++)
    {
        read(x[i]);read(y[i]);read(w[i]);
    }
    LD rx=(LD)(rand()%20000000-10000000)/(LD)1000;
    LD ry=(LD)(rand()%20000000-10000000)/(LD)1000;
    LD val=calc(rx,ry);
    dfs(rx,ry,val,100000);
    return 0;
}

法二

物理背景的题目为什么不考虑物理方法呢?
先随机一个点,计算这个点受的合力,计算方法就是二维计算几何,一个向量表示力,极角表示方向,长度表示大小。然后计算合力。将这个点向那个方向移动。
需要注意的是移动过程中合力方向会发生变化,所以不能移动太远,移动一定距离就重新计算合力。这里设几个参数,调整一下就
可以A了,而且还很快。

有更神的做法欢迎留言。

Comments

comments powered by Disqus