emm

Problem

https://www.luogu.org/problemnew/show/CF995C

Solution

起始答案随机（重要）

温度设高点（模拟起火）

乱搞

乱搞比赛真 tm 刺激

震惊，灭火员出锅

Code

// Code by ajcxsu
// Problem: 995C

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
double x[N], y[N];
double X[N], Y[N];
bool SX[N], SY[N];
bool AX[N], AY[N];
double totx, toty, ax=1e8, ay=1e8;

double len(double x, double y) { return sqrt(x*x+y*y); }
int randint(int l, int r) { return rand()%(r-l+1)+l; }
int n;

void fafa() {
    memcpy(X, x, sizeof(X)), memcpy(Y, y, sizeof(Y)), memset(SX, 0, sizeof(SX));
    double T=10000000, V=0.9995, nx=totx, ny=toty, delta;
    for(int i=0;i<n;i++)
    {
        SX[i]=rand()%2;
        if (SX[i])
        {
            nx-=2*X[i], ny-=2*Y[i];
            X[i]=-X[i];
            Y[i]=-Y[i];
        }
    }
    int r;
    while(T>1e-15) {
        r=randint(0, n-1);
        delta=len(nx-2*X[r], ny-2*Y[r])-len(nx, ny);
        if(delta<0) nx-=2*X[r], ny-=2*Y[r], X[r]=-X[r], Y[r]=-Y[r], SX[r]^=1;
        else if(exp(-delta/T)*RAND_MAX>rand()) nx-=2*X[r], ny-=2*Y[r], X[r]=-X[r], Y[r]=-Y[r], SX[r]^=1;
        T*=V;
    }
    if(len(ax, ay)>len(nx, ny)) {
        ax=nx, ay=ny;
    }
}

int main() {
    ios::sync_with_stdio(false);
    srand((int)new int);
    cin>>n;
    for(int i=0;i<n;i++) cin>>x[i]>>y[i], totx+=x[i], toty+=y[i];
    for(;len(ax, ay)>1.5e6;) fafa();
    for(int i=0;i<n;i++) cout<<(SX[i]?-1:1)<<' ';
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-cf-995c.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆