求助 三分法TLE5~10
查看原帖
求助 三分法TLE5~10
721928
cats142857楼主2022/8/14 19:21
#include <bits/stdc++.h>
using namespace std;
struct point{
	double x;
	double y;
}p[1000000];
const double eps=1e-10;
int n,flag=0;
int sgn(double x){
	if(x>eps)return 1;
	if(x<-eps)return -1;
	return 0;
}
double dist(point a,point b){
	return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
double maxdist(double x,double y){
	int i;
	double maxd=0.0f,d;
	point px;
	px.x=x;
	px.y=y;
	for(i=0;i<n;i++)
	{
		d=dist(px,p[i]);
		if(maxd<d)maxd=d;
	}
	return maxd;
}
double dvy(double x){
	double st,en,tmp1,tmp2,stans,enans,ans1,ans2;
	st=-100000.1f;
	en=100000.1f;
	stans=300000.0f;
	enans=300000.0f;
	while(en-st>eps)
	{
		tmp1=(2*st+en)/3;
		tmp2=(st+2*en)/3;
		ans1=maxdist(x,tmp1);
		ans2=maxdist(x,tmp2);
		if(sgn(stans-ans1)==1&&sgn(ans1-ans2)==1&&sgn(ans2-enans)>-1)
		{
			st=tmp2;
			stans=ans2;
		}
		else if(sgn(stans-ans1)<1&&sgn(ans1-ans2)==-1&&sgn(ans2-enans)==-1)
		{
			en=tmp1;
			enans=ans1;
		}
		else if(sgn(ans1-ans2)==1)
		{
			st=tmp1;
			stans=ans1;
		}
		else
		{
			en=tmp2;
			enans=ans2;
		}
	}
	if(flag==1)cout<<st<<' ';
	return stans;
}
int main(int argc, char** argv) {
	ios::sync_with_stdio(false),cin.tie(0);
	cout<<setiosflags(ios::fixed)<<setprecision(2);
	int i;
	double st,en,tmp1,tmp2,stans,enans,ans1,ans2;
	cin>>n;
	for(i=0;i<n;i++)cin>>p[i].x>>p[i].y;
	st=-100000.1f;
	en=100000.1f;
	stans=300000.0f;
	enans=300000.0f;
	while(en-st>eps)
	{
		tmp1=(2*st+en)/3;
		tmp2=(st+2*en)/3;
		ans1=dvy(tmp1);
		ans2=dvy(tmp2);
		if(sgn(stans-ans1)>-1&&sgn(ans2-enans)>-1)
		{
			st=tmp2;
			stans=ans2;
		}
		else if(sgn(stans-ans1)<1&&sgn(ans2-enans)<1)
		{
			en=tmp1;
			enans=ans1;
		}
		else if(sgn(ans1-ans2)==1)
		{
			st=tmp1;
			stans=ans1;
		}
		else
		{
			en=tmp2;
			enans=ans2;
		}
	}
	cout<<st<<' ';
	flag=1;
	dvy(st);
	cout<<stans<<'\n'; 
	return 0;
}
2022/8/14 19:21
加载中...