# 【BZOJ3680】吊打XXX 狭义费马点 模拟退火

www.MyException.Cn  网友分享于：2015-02-11  浏览：0次
【BZOJ3680】吊打XXX 广义费马点 模拟退火

```#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/43526909");
}
```

！！！其实我脸一点也不黑！我天天洗脸的！

```#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10100
#define inf 23333333333333333ll
#define eps 1e-3
#define down 0.993
using namespace std;
double ln,rn,lm,rm;
struct Point // 点
{
double x,y,z; // 坐标、该点作为结束点的答案。
Point(double _x=0.0,double _y=0.0):x(_x),y(_y){}
bool in()
{
if(x<ln||x>rn)return 0;
if(y<lm||y>rm)return 0;
return 1;
}
}P[N],now,ans;
int p;
inline double Rand(){return ((double)(rand()%1000+1.0))/1000.0;}
inline void init()
{
double tempx=0.0,tempy=0.0;
for(int i=1;i<=p;i++)
{
tempx+=P[i].x,tempy+=P[i].y;
ln=min(P[i].x,ln),rn=max(P[i].x,rn);
lm=min(P[i].y,lm),rm=max(P[i].y,rm);
}
now=Point(tempx/p,tempy/p);
ans.z=inf;
}
inline double calc(const Point &a,const Point &b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double Calc(Point &a)
{
a.z=0.0;
for(int i=1;i<=p;i++)a.z+=calc(P[i],a)*P[i].z;
if(a.z<ans.z)ans=a;
return a.z;
}
Point newpos(double T,const Point &a)
{
double alp=2.0*acos(-1.0)*Rand();
return Point(a.x+T*cos(alp)*Rand(),a.y+T*sin(alp)*Rand());
}
void Std_Anne(double T=sqrt((rn-ln)*(rn-ln)+(rm-lm)*(rm-lm))*0.3)
{
for(;T>eps;T*=down)
{
Point next=newpos(T,now);
if(next.in())
{
double dis=Calc(now)-Calc(next);
if(exp(dis/T)>=Rand())now=next;
}
}
}
void ioi()
{
for(int i=1;i<=1000;i++)
{
Point next=newpos(0.001,ans);
if(next.in())
{
double dis=Calc(next)-Calc(now);
if(dis>0)now=next;
}
}
}
int main()
{
freopen("test.in","r",stdin);
srand(20134858);
scanf("%d",&p);
for(int i=1;i<=p;i++)scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].z);
init();
Std_Anne(1000000.0);
ioi();
printf("%.3lf %.3lf\n",ans.x,ans.y);
return 0;
}
```