自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:51:39，当前版本为作者最后更新于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;
}