我将
∑i=1n∣x−xi∣+∣y−yi∣−di
作为系统能量(x,y)为当前点,但是最后一个数据点怎么调参都过不去。有没有大佬帮忙看一看。
有注释的代码:
#include <bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
#define N 1010
struct node{
int x,y,d;
}a[N];
int n,sx,sy,tot;
int ansx,ansy,anss; //全局最优解的坐标,anss记录解的数量
double ans=1e18,t; //全局最优解、温度
const double delta=0.97; //降温系数
inline int calc(int x,int y) { //计算整个系统的能量
int rt=0;
for (re int i=1;i<=n;i++) {
rt+=abs(abs(x-a[i].x)+abs(y-a[i].y)-a[i].d);
}
if(rt==0){
for(int i=1;i<=anss;i++){//看看这个解之前有没有
if(x==ans1[i].x && y==ans1[i].y) return rt;
}
ans1[++anss].x=x;//没有的话添加这个解
ans1[anss].y=y;
}
return rt;
}
inline void simulate_anneal() { //SA主过程
int x=ansx,y=ansy;
t=1000; //初始温度
while (t>1e-14) {
int X=((ll)x+(ll)((((rand()<<1)-RAND_MAX)*t)))%4000007;
int Y=((ll)y+(ll)(((rand()<<1)-RAND_MAX)*t))%4000007; //得出一个新的坐标
int now=calc(X,Y);
int Delta=now-ans;
if (Delta<0) { //接受
x=X,y=Y;
ansx=x,ansy=y,ans=now;
}
else if (exp(-Delta/t)*RAND_MAX>rand()) x=X,y=Y; //以一个概率接受
t*=delta;
}
}
inline void Solve() {
while(!anss) simulate_anneal();
simulate_anneal();
simulate_anneal();
}
int main() {
srand(time(0));
n=read();
for (re int i=1;i<=n;i++) {
a[i].x=read(),a[i].y=read(),a[i].d=read();
}
Solve();
if(anss==1) printf("%d %d\n",ansx,ansy);
if(anss>1) printf("uncertain\n");
if(!anss) printf("impossible");
return 0;
}