最小半径圆.cpp

里面包括了一些acm比赛是常用的函数

#include "stdio.h"
#include "math.h"
#include "string.h"
#include "iostream.h"
#define  maxn 1000
#define EPS 1e-6
typedef struct{
	double x,y;
}TPoint;
typedef struct
{
   double r;
   TPoint centre;
}TCircle;
TPoint TTriangle[3];
TPoint TCircleEdge[3];
TPoint Tlist[maxn+1];


int casenum,n;
//Tlist a;
TPoint  a[maxn+1];
TCircle c;

double distance(TPoint p1,TPoint p2)
{return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}

double triangleArea(TTriangle t)
{
	return fabs(t[0].x*t[1].y+t[1].x*t[2].y+t[2].x*t[0].y-
		t[1].x*t[0].y-t[2].x*t[1].y-t[0].x*t[2].y)/2;
} 


TCircle circleOfTriangle(TTriangle t)
{
	TCircle tmp;
	double a,b,c,c1,c2;
	double xA,yA,xB,yB,xC,yC;
	a=distance(t[0],t[1]);
	b=distance(t[1],t[2]);
	c=distance(t[2],t[0]);
	tmp.r=a*b*c/triangleArea(t)/4;
	xA=t[0].x;yA=t[0].y;
    xB=t[1].x;yB=t[1].y;
	xC=t[2].x;yC=t[2].y;
	c1=(xA*xA+yA*yA-xB*xB-yB*yB)/2;
	c2=(xA*xA+yA*yA-xC*xC-yC*yC)/2;
	tmp.centre.x=(c1*(yA-yC)-c2*(yA-yB))/
		         ((xA-xB)*(yA-yC)-(xA-xC)*(yA-yB));
	tmp.centre.y=(c1*(xA-xC)-c2*(xA-xB))/
		         ((yA-yB)*(xA-xC)-(yA-yC)*(xA-xB));
	return tmp;
}
void init()
{
   int i;
   //scanf("%d",&n);
   cin>>n;
   memset(a,0,sizeof(a));
   for(i=1;i<=n;i++)
	   cin>>a[i].x>>a[i].y;
}
TCircle MinCircle2(int tce,TCircleEdge ce)
{
	TCircle tmp;
	memset(tmp,0,sizeof(tmp));
	switch(tce)
	{
	case 0:tmp.r=-2;break;
	case 1:tmp.centre=ce[0];break;
	case 2:
		tmp.r=distance(ce[0],ce[1])/2;
	    tmp.centre.x=(ce[0].x+ce[1].x)/2;
		tmp.centre.y=(ce[0].y+ce[1].y)/2;
   	    break;
    case 3:tmp=circleOfTriangle(ce);break;	
	}
  return tmp;
}
void swap(TPoint x,TPoint y)
{
	TPoint  z;
	z=x;x=y;y=z;
}
bool inCircle(TPoint p,TCircle c)
{
	return distance(p,c.centre)<c.r+EPS;
}


void MinCircle(int t,int tce,TCircleEdge ce)
{
   int i,j;
   TPoint tmp;
   c=MinCircle2(tce,ce);
   if(tce==3)  break;
   for(i=1;i<=t;i++)
   {
	   if(distance(a[i],c.centre)>c.r+EPS)
	   {
		   ce[tce]=a[i];
		   MinCircle(i-1,tce+1,ce);
		   tmp=a[i];
		   for(j=i;j>=2;j--)
			   a[j]=a[j-1];
		   a[1]=tmp;
	   }
}
void run()
{
   TCircleEdge ce;
   int i;
   MinCircle(n,0,ce);
   cout<<c.centre.x<<' '<<c.centre.y<<' '<<c.r<<endl;
}
void main()
{
	cin>>casenum;
	while(casenum>0)
	{
		init;
		run;
		dec(casenum);
	}
}
}