1450.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
class point{
public:
	double x,y;
	point(){}
	point(double a,double b){x=a;y=b;}
};
class midcircle{
public:
    double x,y,rr;
	midcircle(){}
	midcircle(double a,double b,double c){x=a;y=b;rr=c;}
};
bool incircle(const point & p,const double & x,const double & y,const double & rr){
    return((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y)-rr<1e-14);
}
double disrr(const point & a,const point & b){
    return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
midcircle makecircle(const point & a,const point & b,const point & c){
    midcircle res(0,0,0);    
	double x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6,a1,a2,b1,b2,c1,c2;        
	           x1 = a.x; x2 = b.x; x3 = c.x; 
               y1 = a.y; y2 = b.y; y3 = c.y; 
               x4 = (x1 + x2) / 2; x5 = (x1 + x3) / 2; x6 = (x2 + x3) / 2; 
               y4 = (y1 + y2) / 2; y5 = (y1 + y3) / 2; y6 = (y2 + y3) / 2; 
               a1 = x2 - x1; b1 = y2 - y1; c1 = y4 * (y2 - y1) + x4 * (x2 - x1); 
               a2 = x3 - x1; b2 = y3 - y1; c2 = y5 * (y3 - y1) + x5 * (x3 - x1); 
               if((b1 * a2 - a1 * b2) == 0) 
                  return res; 
               res.x = (b1 * c2 - b2 * c1) / (b1 * a2 - a1 * b2); 
               res.y = (c1 * a2 - a1 * c2) / (b1 * a2 - a1 * b2); 
               res.rr = (a.x-res.x)*(a.x-res.x)+(b.y-res.y)*(b.y-res.y); 
    return res;
}
int cmp(const midcircle & a,const midcircle & b){
    return a.rr<b.rr;
}
int main(){
   //ifstream cin("in1450.txt");
   int i,j,k,n,flag;
   double x,y,rr;
   while(cin>>n&&n){
	   if(n==1){
		   cin>>x>>y;
		   cout<<setiosflags(ios::fixed)<<setprecision(2)<<x<<" "<<setprecision(2)<<y<<" 0.00\n";
	   }
	   else{
           vector<point> vec(n);
		   for(i=0;i<n;i++) cin>>vec[i].x>>vec[i].y;
           //找距离最长的两点
		   vector<int> maxdispoint;
		   x=-1;
		   for(i=0;i<n-1;i++)
			   for(flag=i+1;flag<n;flag++){
				   y=disrr(vec[i],vec[flag]);
				   if(y>x){
					   maxdispoint.clear();
					   maxdispoint.push_back(i);
                       maxdispoint.push_back(flag);
					   x=y;
				   }
				   else if(y==x){
					   maxdispoint.push_back(i);
                       maxdispoint.push_back(flag);
				   }
			   }
		   rr=x/4;
		   for(j=0;j<maxdispoint.size();j+=2){
		      x=(vec[maxdispoint[j]].x+vec[maxdispoint[j+1]].x)/2;y=(vec[maxdispoint[j]].y+vec[maxdispoint[j+1]].y)/2;flag=1;
			  for(i=0;i<n;i++)
			     if(!incircle(vec[i],x,y,rr)){
                  flag=0;break;
				 }
			  if(flag) break;
		   }
		   if(flag) cout<<setiosflags(ios::fixed)<<setprecision(2)<<x<<" "<<setprecision(2)<<y<<" "<<setprecision(2)<<sqrt(rr)<<"\n";
		   else{
               vector<midcircle> veccircle;
			   for(i=0;i<n-2;i++)
				   for(j=i+1;j<n-1;j++)
					   for(k=j+1;k<n;k++)
                               veccircle.push_back(makecircle(vec[i],vec[j],vec[k]));
			   sort(veccircle.begin(),veccircle.end(),cmp);
			   for(i=0;i<veccircle.size();i++)
				   if(veccircle[i].rr>rr){
                       flag=1;
					   for(j=0;j<n;j++)
                          if(!incircle(vec[j],veccircle[i].x,veccircle[i].y,veccircle[i].rr)){
                             flag=0;break;
						  }
					   if(flag) break;
				   }
               cout<<setiosflags(ios::fixed)<<setprecision(2)<<veccircle[i].x<<" "<<setprecision(2)<<veccircle[i].y<<" "<<setprecision(2)<<sqrt(veccircle[i].rr)<<"\n";
		   }
	   }
   }
   return 0;
}