题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

· · 题解

不会退火也能做的退火题

被同机房的\color{red}{F}\color{black}{lamire}推荐了这么一道题

然后我作为不会退火的垃圾,开始按题意模拟

思路:每一次向合力方向移动,直到平衡

首先就是写了一地的函数

struct point
{
    double x,y;
    friend point operator + (point a,point b)
    {
        point c;
        c.x=a.x+b.x;
        c.y=a.y+b.y;
        return c;
    }
    void read(int a,int b)
    {
        x=a;
        y=b;
    }
    void print()
    {
        printf("point:%lf %lf\n",x,y);
    }
} p[1001];
double point_dis(point a,point b)//point_dis指点间距离
{
    double d1=a.x-b.x;
    double d2=a.y-b.y;
    return sqrt(d1*d1+d2*d2);
}
double point_cos(point a,point b)
{
    return (b.x-a.x)/point_dis(a,b);
}
double point_sin(point a,point b)//,point_cos/sin描述两点间角度的余弦/正弦
{
    return (b.y-a.y)/point_dis(a,b);
}
point point_force(point s,point t,double w)s受到t方向w的力,分解为两个方向
{
    point c;
    c.x=point_cos(s,t)*w;
    c.y=point_sin(s,t)*w;
    return c;
}

然后开始调主函数 一代目:

for(int i=1; i<=10000; i++)
    {
        mv.read(0,0);
        for(int j=1; j<=n; j++)
        {
            if(now.x==p[j].x && now.y==p[j].y)
            {
                if(abss(now.x)<=0.001)
                {
                    now.x=0;
                }
                if(abss(now.y)<=0.001)
                {
                    now.y=0;
                }
                printf("%.3lf %.3lf\n",now.x,now.y);
                return 0;
            }
            mv=mv+point_force(now,p[j],w[j]);
        }
        now=now+mv;
    }

此时mv(即合力)过大,导致维护的当前位置经常在两点间左右横跳

所以得到二代目:

for(int i=1; i<=10000; i++)
    {
        mv.read(0,0);
        for(int j=1; j<=n; j++)
        {
            if(now.x==p[j].x && now.y==p[j].y)
            {
                if(abss(now.x)<=0.001)
                {
                    now.x=0;
                }
                if(abss(now.y)<=0.001)
                {
                    now.y=0;
                }
                printf("%.3lf %.3lf\n",now.x,now.y);
                return 0;
            }
            mv=mv+point_force(now,p[j],w[j]);
        }
        mv.x/=100;
        mv.y/=100;
        now=now+mv;
    }

想都别想,不是步数内爬不完就是TLE

最后就按照前一些步数加速爬行,后面逐渐放缓,成功AC

最后贴上代码,完结撒花

#include <bits/stdc++.h>
//#include <windows.h>
//#define int long long
using namespace std;
struct point
{
    double x,y;
    friend point operator + (point a,point b)
    {
        point c;
        c.x=a.x+b.x;
        c.y=a.y+b.y;
        return c;
    }
    void read(int a,int b)
    {
        x=a;
        y=b;
    }
} p[1001];
int x[1001];
int y[1001];
int w[1001];
int n;
double point_dis(point a,point b)
{
    double d1=a.x-b.x;
    double d2=a.y-b.y;
    return sqrt(d1*d1+d2*d2);
}
double point_cos(point a,point b)
{
    return (b.x-a.x)/point_dis(a,b);
}
double point_sin(point a,point b)
{
    return (b.y-a.y)/point_dis(a,b);
}
point point_force(point s,point t,double w)
{
    point c;
    c.x=point_cos(s,t)*w;
    c.y=point_sin(s,t)*w;
    return c;
}
point now;
point mv;
point org;
double sum;
double qwq;
double abss(double a)
{
    return a<0?-a:a;
}
int main()
{
    org.read(0,0);
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&w[i]);
        sum+=w[i];
        p[i].read(x[i],y[i]);
    }
    srand(time(0));
    now.x=rand()%2000;
    now.y=rand()%2000;
    now.x-=1000;
    now.y-=1000;
    for(int i=1; i<=10000; i++)
    {
        mv.read(0,0);
        for(int j=1; j<=n; j++)
        {
            if(now.x==p[j].x && now.y==p[j].y)
            {
                if(abss(now.x)<=0.001)
                {
                    now.x=0;
                }
                if(abss(now.y)<=0.001)
                {
                    now.y=0;
                }
                printf("%.3lf %.3lf\n",now.x,now.y);
                return 0;
            }
            mv=mv+point_force(now,p[j],w[j]);
        }
        qwq=point_dis(mv,org);
        if(i>=2000)
        {
            mv.x/=(i/2)-999;
            mv.y/=(i/2)-999;
        }
        else if(qwq>=sum*7/8)
        {
            mv.x*=10;
            mv.y*=10;
        }
        else if(qwq>=sum*3/4)
        {
            mv.x*=2;
            mv.y*=2;
        }
        now=now+mv;
    }
    if(abss(now.x)<=0.001)
    {
        now.x=0;
    }
    if(abss(now.y)<=0.001)
    {
        now.y=0;
    }
    printf("%.3lf %.3lf\n",now.x,now.y);
    return 0;
}