Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

火候欠佳啊。wa了好久。。。

Posted by huxinjie at 2011-08-21 13:46:18 on Problem 2069
#include <iostream>
#include <math.h>
using namespace std;
#define  eps 1e-7
struct node
{
	double x,y,z;
};
node mm[50];
node ppx[20];
double dist(node aa,node bb)
{
	return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y)+(aa.z-bb.z)*(aa.z-bb.z));
}
double cal(node p,int k)
{
	double dis;
	dis=0;
	for(int i=0;i<k;i++)
	{
		dis=max(dis,dist(p,mm[i]));
	}
	return dis;
}
void work(int p,int k,double now)
{
	for(int i=0;i<p;i++)
	{
		ppx[i].x=(rand()%10000+1)/10000.0*100;
		ppx[i].y=(rand()%10000+1)/10000.0*100;
		ppx[i].z=(rand()%10000+1)/10000.0*100;
	}
	node d;
	double dis,len;
	int t;
	while(now>eps)
	{
		for(int i=0;i<p;i++)
		{
			dis=0;
			for(int j=0;j<k;j++)
			{
				len=dist(ppx[i],mm[j]);
				if(dis<len)
				{
					dis=len;
					t=j;
				}
			}
			ppx[i].x+=(mm[t].x-ppx[i].x)/dis*now;
			ppx[i].y+=(mm[t].y-ppx[i].y)/dis*now;
			ppx[i].z+=(mm[t].z-ppx[i].z)/dis*now;
		}
		now*=0.99;
	}
}
int main ()
{
//	freopen("in.txt","r",stdin);
	int n;
	double dis,now;
	node p;
	while(scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf%lf",&mm[i].x,&mm[i].y,&mm[i].z);
		}
		work(10,n,150);
		dis=1e50;
		for(int i=0;i<10;i++)
		{
			dis=min(dis,cal(ppx[i],n));
		}
		printf("%.5lf\n",dis);
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator