P3691: The failure of Simulated Annealing

035966_L3 · 2024-11-20 21:35:46 · 题解

题解区在写什么啊？

每次均匀随机生成定点 (x,y) 和倾斜角 \theta，暴力找最优解。

该做法的正确率可以稳定在 98\% 以上。

相比之下，模拟退火甚至不能稳定 AC。

AC Code：

#include <bits/stdc++.h>
using namespace std;
double x[100012],y[100012];
int z[100012];
int check(int n,double dk,double db)
{
    dk=tan(dk);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(y[i]>dk*x[i]+db&&z[i]==1) ans++;
        if(y[i]<=dk*x[i]+db&&z[i]==-1) ans++;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    srand(time(0));
    int n,m,k;
    cin>>n>>m>>k;
    double bk=1,bb=0;
    int bm=0;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i]>>z[i];
    for(int i=n;i<=100000000;i+=n)
    {
        double dk=rand()*1000000.0/RAND_MAX;
        double dx=rand()*100.0/RAND_MAX;
        double dy=rand()*100.0/RAND_MAX;
        double db=dy-dx*tan(dk);
        int dm=check(n,dk,db);
        if(dm>bm) bm=dm,bk=dk,bb=db;
    }
    int et=100000000*(1.9/(clock()*1.0/CLOCKS_PER_SEC));
    if(k>=2&&k<=5) et=100000000*(0.95/(clock()*1.0/CLOCKS_PER_SEC));
    for(int i=100000000;i<=et;i+=n)
    {
        double dk=rand()*1000000.0/RAND_MAX;
        double dx=rand()*100.0/RAND_MAX;
        double dy=rand()*100.0/RAND_MAX;
        double db=dy-dx*tan(dk);
        int dm=check(n,dk,db);
        if(dm>bm) bm=dm,bk=dk,bb=db;
    }
    bk=tan(bk);
    for(int i=1;i<=m;i++)
    {
        double x,y;
        cin>>x>>y;
        if(y>bk*x+bb) puts("1");
        else puts("-1");
    }
    return 0;
}