BZOJ 3680 吊打

发表于 | 更新于

Link

至于这个就比模拟退火更玄学了。。几乎完全取决于一开始选择的起点。。不得要领。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10000+100;
template <class T> inline T sqr(T x){return x*x;}
struct poi{int x,y;}p[MAXN];int w[MAXN],n;
double calc(double x,double y)
{
	double res=0;
	for(int i=1;i<=n;i++) res+=sqrt(sqr(x-p[i].x)+sqr(y-p[i].y))*w[i];
	return res;
}
double frand()
{
	return ((double)rand()/RAND_MAX)*(rand()&1?1:-1);
}
int main()
{
	srand(522133279);
	get(n);double x=0,y=0;
	for(int i=1;i<=n;i++) 
	{
		get(p[i].x),get(p[i].y),get(w[i]);
		//x+=p[i].x*w[i],y+=p[i].y*w[i];
		x+=p[i].x,y+=p[i].y;
	}
	x/=n,y/=n;double ANS=calc(x,y),cx=x,cy=y,tx,ty;
	for(double step=1e5;step>1e-5;step*=0.98)
	{
		tx=cx+frand()*step,ty=cy+frand()*step;
		double res=calc(tx,ty);
		if(chkmn(ANS,res))
			x=tx,y=ty;
		if(calc(cx,cy)>res)
			cx=tx,cy=ty;
	}
	printf("%.3lf %.3lf\n",x,y);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */