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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*
hdu2899
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const double eps=1e-9;
int Case;
double y;
double f(double x)
{
	double x_2=x*x;
	double x_3=x*x*x;
	double x_6=x_3*x_3;
	double x_7=x_6*x;
	 return 6.0*x_7+8.0*x_6+7.0*x_3+5.0*x_2-y*x;
}
const int maxt=43;
const int numt=33;
double tx[maxt];
bool valid(double x)
{
	return x>eps&&x<100-eps;
}
double minv[maxt];
void initTx()
{
	for(int i=1;i<=numt;++i)
	{
		tx[i]=double(rand()%100+1);
		minv[i]=f(tx[i]);
	}
}
double ans;
void solve()
{
	ans=1e60;
	initTx();
	for(double T=100.0;T>1e-7;T*=0.93)
	{
		for(int i=1;i<=numt;++i)
		{
			for(int j=-1;j<=1;j+=2)
			{
				double t=tx[i]+j*T;
				if(valid(t))
				{
					double tv=f(t);
					if(tv<minv[i])
					{
						minv[i]=tv,tx[i]=t;
						if(tv<ans)
							ans=tv;
					}
				}
			}
		}
	}
}
int main()
{
	freopen("hdu2899_1.in","r",stdin);
	//freopen("hdu2899.out","w",stdout);
	for(scanf("%d",&Case);Case;--Case)
	{
		scanf("%lf",&y);
		solve();
		printf("%.4lf\n",ans);
	}
	return 0;
}

  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

/*
hdu3007
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const double eps=1e-9;
void read(int& A);
struct POINT
{
	double x,y;
	inline POINT(){x=y=0;}
	inline POINT(double xx,double yy):x(xx),y(yy){}
	inline void inPut(){scanf("%lf%lf",&x,&y);}
}point[503];
struct LINE
{
	POINT p1,p2;
	inline LINE(){}
	inline LINE(POINT pp1,POINT pp2):p1(pp1),p2(pp2){}
	inline void inPut(){p1.inPut(),p2.inPut();}
	inline void init(POINT pp1,POINT pp2){p1=pp1,p2=pp2;}
	inline int dx(){return p2.x-p1.x;}
	inline int dy(){return p2.y-p1.y;}
};

int n;
template<typename T>
inline bool Min(T a,T b){return a>b?b:a;}
template<typename T>
inline bool Max(T a,T b){return a<b?b:a;}
template<typename T>
inline T Abs(T a){return a<0?-a:a;}
inline double dis(POINT a,POINT b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline POINT mid(POINT a,POINT b)
{
	return POINT((a.x+b.x)/2,(a.y+b.y)/2);
}
/*
inline POINT cross(LINE a,LINE b)
{
	double 
	Cabd=(crossPdt(a.p1,a.p2,b.p2)),
	Cabc=(crossPdt(a.p1,b.p1,a.p2));
	double
  	x=(Cabd*b.p1.x+Cabc*b.p2.x)/(Cabd+Cabc),
  	y=(Cabd*b.p1.y+Cabc*b.p2.y)/(Cabd+Cabc);
  	//cout<<Cabd+Cabc<<endl;
	return POINT(x,y);
}
*/
struct CIRCLE
{
	POINT O;
	double r;
	inline CIRCLE(){r=0;}
	inline CIRCLE(POINT a,double rr):O(a),r(rr){}
	inline void clear(){O.x=O.y=r=0;}
	inline void init(POINT a,double rr){O=a,r=rr;}
	inline void outPut(){printf("%.2f %.2f %.2f\n",O.x,O.y,r);}
	inline void init(POINT a,POINT b)//two point as d
	{
		r=dis(a,b)/2.0;
		O=mid(a,b);
	}
	inline void init(POINT a,POINT b,POINT c)
	{
		double 
  		c1=(a.x*a.x+a.y*a.y-b.x*b.x-b.y*b.y)/2.0,
  		c2=(a.x*a.x+a.y*a.y-c.x*c.x-c.y*c.y)/2.0,
  		x=(c1*(a.y-c.y)-c2*(a.y-b.y))/((a.x-b.x)*(a.y-c.y)-(a.x-c.x)*(a.y-b.y)),
  		y=(c1*(a.x-c.x)-c2*(a.x-b.x))/((a.y-b.y)*(a.x-c.x)-(a.y-c.y)*(a.x-b.x));
  		O=POINT(x,y);
 		r=dis(O,a);
	}
	inline bool inCircle(POINT p)
	{
		return dis(p,O)+eps<r;
	}
	inline bool onCircle(POINT p)
	{
		return Abs(r-dis(p,O))<eps;
	}
	inline bool outCircle(POINT p)
	{
		return dis(O,p)>r+eps;
	}

};
CIRCLE now;
int main()
{
	//freopen("hdu3007.in","r",stdin);
	//freopen("hdu3007.out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		now.clear();
		for(int i=1;i<=n;++i)
		{
			point[i].inPut();
		}
		now.init(point[1],point[2]);
		for(int i=3;i<=n;++i)
		{
			if(now.outCircle(point[i]))
			{
				now.O=point[i];
				for(int j=1;j<=i-1;++j)
				{
					if(now.outCircle(point[j]))
					{
						now.init(now.O,point[j]);
						for(int k=1;k<=j-1;++k)
						{
							if(now.outCircle(point[k]))
							{
								now.init(point[i],point[j],point[k]);
							}
						}
					}
				}
			}
		}
		now.outPut();
	}
	return 0;
}
void read(int& A)
{
	char r;bool f=false;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')f=true,r=getchar();
	for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
	if(f)A=-A;
}

 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/*
poj2069
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const double dinf=1e60;
const double eps=1e-9;
const int maxn=33;
int n;

struct P
{
	double x,y,z;
	P():x(0),y(0),z(0){}
	P(double xx,double yy,double zz):x(xx),y(yy),z(zz){}
	void getin()
	{
		scanf("%lf%lf%lf",&x,&y,&z);
	}
}p[maxn];
double dis(const P& a,const P& b)
{
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	double dz=a.z-b.z;
	return sqrt(dx*dx+dy*dy+dz*dz);
}
void input()
{
	for(int i=1;i<=n;++i)
	{
		p[i].getin();
	}
}
double ans;
void solve()
{
	ans=dinf;
	P o(0,0,0);
	for(double T=100.0;T>eps;T*=0.98)//if TLE, try to change eps
	{
		double maxd=0;int id;
		for(int i=1;i<=n;++i)
		{
			double td=dis(o,p[i]);
			if(td>maxd)
				maxd=td,id=i;
		}
		if(maxd<ans)
			ans=maxd;
			//cout<<maxd<<endl;
		o.x+=(p[id].x-o.x)/maxd*T;
		o.y+=(p[id].y-o.y)/maxd*T;
		o.z+=(p[id].z-o.z)/maxd*T;
	}
}
int main()
{
	freopen("poj2069_1.in","r",stdin);
	//freopen("poj2069.out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		input();
		solve();
		printf("%.5lf\n",ans);
	}
	return 0;
}

  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/*
poj1379
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();r!='-'&&(r<48||r>57);r=getchar());
	if(r=='-')f=-1,r=getchar();
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxx=10003;
const int maxn=1003;
const int maxt=33;
int T,X,Y,n;

struct P 
{
	double x,y;
	void init(int xx,int yy)
	{
		x=(double)xx,y=(double)yy;
	}
	void getin()
	{
		//read(x),read(y);
		scanf("%lf%lf",&x,&y);
	}
	void Try(P p,double t,double d)
	{
		x=p.x+cos(t)*d;
		y=p.y+sin(t)*d;
	}
	bool valid()
	{
		return x>=0.0&&y>=0.0&&x<=double(X)&&y<=double(Y);
	}
}hole[maxn],tp[maxt];
double dis(const P& a,const P& b)
{
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
double mindis(const P& p)
{
	double md=1e60;
	for(int i=1;i<=n;++i)
	{
		double td=dis(hole[i],p);
		if(td<md)
			md=td;
	}
	return md;
}
void input()
{
	read(X),read(Y),read(n);
	for(int i=1;i<=n;++i)
	{
		hole[i].getin();
	}
}
double d[maxn];
void InitTp()
{
	for(int i=1;i<=30;++i)
	{
		tp[i].init(rand()%X+1,rand()%Y+1);
		d[i]=mindis(tp[i]);
	}
}

P ans;
void solve()
{
	InitTp();
	P o;
	for(double T=Max(X,Y)/sqrt(double(n))+1;T>1e-2;T*=0.88)
	{
		for(int i=1;i<=30;++i)
		{
			for(int j=1;j<=30;++j)
			{
				o.Try(tp[i],rand(),T);
				double md=mindis(o);
				if(o.valid()&&md>d[i])
					tp[i]=o,d[i]=md;
			}
		}
		//cout<<T<<endl;
	}
	int id=1;
	for(int i=2;i<=30;++i)
	{
		if(d[i]>d[id])
			id=i;
	}
	ans=tp[id];
}
int main()
{
	freopen("poj1379_1.in","r",stdin);
	//freopen("poj1379.out","w",stdout);
	for(read(T);T;--T)
	{
		input();
		solve();
		printf("The safest point is (%.1lf, %.1lf).\n", ans.x,ans.y);
	}
	return 0;
}

  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

/*
poj2420
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w) 
{
	char r;int f=1;
	for(r=getchar();r!='-'&&(r<48||r>57);r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=103;
const int maxt=43;
const int numt=33;
int n;
int X=0,Y=0;
struct P
{
	double x,y;
	void init(double xx,double yy)
	{
		x=xx,y=yy;
	}
	void getin()
	{
		int xx,yy;
		read(xx),read(yy);
		x=double(xx),y=double(yy);
	}
	void Try(const P& p,double r)
	{
		double theta=rand();
		x=p.x+cos(theta)*r;
		y=p.y+sin(theta)*r;
	}
}p[maxn],tp[maxt];
double dis(const P& a,const P& b)
{
	double dx=a.x-b.x,dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
void input()
{
	read(n);
	for(int i=1;i<=n;++i)
	{
		p[i].getin();
		if(p[i].x>X)X=p[i].x;
		if(p[i].y>Y)Y=p[i].y;
	}
}
double sumdis(const P& x)
{
	double sum=0.0;
	for(int i=1;i<=n;++i)
	{
		sum+=dis(p[i],x);
	}
	return sum;
}
double d[maxt];
void initTp()
{
	for(int i=1;i<=numt;++i)
	{
		tp[i].init(rand()%X+1,rand()%Y+1);
		d[i]=sumdis(tp[i]);
	}
}
double ans=1e60;
void solve()
{
	initTp();
	P o;
	for(double T=(double)Max(X,Y)+1;T>1e-3;T*=0.93)
	{
		for(int i=1;i<=numt;++i)
		{
			for(int j=1;j<=numt;++j)
			{
				o.Try(tp[i],T);
				double td=sumdis(o);
				if(td<d[i])
				{
					tp[i]=o;
					d[i]=td;
					if(td<ans)
						ans=td;
				}
			}
		}
	}
}
int main()
{
	freopen("poj2420_1.in","r",stdin);
	//freopen("poj2420.out","w",stdout);
	input();
	solve();
	printf("%.0f\n",ans);
	return 0;
}