自动搬运

查看原文

来自洛谷，原作者为

	Mirach 诶这里还可以填东西？

搬运于2025-08-24 21:59:28，当前版本为作者最后更新于2018-04-07 19:08:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem

简要题意：

给定一个极坐标平面，和两个用极坐标表示的点，还有一个根据极坐标得值的函数，求以这两个点为端点的线段上的函数最大值

想要题面和数据可以上code+下载

Solution

一看到题就感觉是数学题，求函数极值，然而那个函数好像很复杂

官方题解是暴力扫描，然而蒟蒻比赛时WA4个点死活改不出来，可能是过程中间出现了nan？

然而这题好像可以用爬山，看看这题的阴影部分，发现亮度分布地比较连续而且没有较多的起伏：

所以可见在这里爬山的准确率还是可以的，好像调调参数可以在800ms内？

具体做法就是在先将极坐标转成直角坐标（可以取$(sin,cos)$坐标），再在线段上取等分点，在每个点上选取当前附近比较亮的地方走，并不断缩小步长，调调参数就能A

具体见代码，用向量可能比较方便

Code

爬山：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))

#define eps (1e-8)
#define pi (3.1415926535897932384626323849)

template <typename _Tp> inline _Tp read(_Tp&x){
	rg char c11=getchar(),ob=0;x=0;
	while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=1;
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

struct vec{
	double x,y;
	vec(){}
	vec(const double&X,const double&Y){x=X,y=Y;}
	inline vec operator + (const vec&t) const {return vec(x+t.x,y+t.y);}
	inline vec operator - (const vec&t) const {return vec(x-t.x,y-t.y);}
	inline vec operator * (const db &t) const {return vec(x*t,y*t);}
	inline void in(){scanf("%lf%lf",&x,&y);}
};

inline vec r_t_p(vec r){
	vec p;
	double m=sqrt(r.x*r.x+r.y*r.y);
	if(fabs(r.x)<eps&&fabs(r.y)<eps)return vec(0,0);
	else if(r.x>=0&&r.y>=0)p.x=asin(r.x/m);
	else if(r.x>=0&&r.y<=0)p.x=pi-asin(r.x/m);
	else if(r.x<=0&&r.y<=0)p.x=pi+asin(-r.x/m);
	else p.x=pi+pi-asin(-r.x/m);
	p.y=m;
	return p;
}

inline vec p_t_r(vec p){return vec(p.y*sin(p.x),p.y*cos(p.x));}

inline double get(vec d){
	int h=d.x/(pi/3);
	double f=d.x/(pi/3)-h;
	double p=1-d.y;
	double q=1-f*d.y;
	double t=1-(1-f)*d.y;
	switch(h){
		case 0:return 1*0.3+t*0.59+p*0.11;
		case 1:return q*0.3+1*0.59+p*0.11;
		case 2:return p*0.3+1*0.59+t*0.11;
		case 3:return p*0.3+q*0.59+1*0.11;
		case 4:return t*0.3+p*0.59+1*0.11;
		case 5:return 1*0.3+p*0.59+q*0.11;
		default : return 0;
	}
}

int main(){
	vec V,Ap,Bp,Ar,Br;
	int T;read(T);while(T--){
		Ap.in();Ap.x=Ap.x*pi/180.0;Ap.y/=100.0;
		Bp.in();Bp.x=Bp.x*pi/180.0;Bp.y/=100.0;
		Ar=p_t_r(Ap);
		Br=p_t_r(Bp);
		V=Br-Ar;
		double t,t1,t2,f1,f2,stp;
		double nxt1,nxt2,ans=0;
		for(rg int i=0;i<101;++i){  //实测这里可以开到50
			t=i/100.0;
			stp=0.5;
			for(rg int j=1;j<=1000;++j){  //实测这里可以开到170
				t1=t+stp,t2=t-stp;
				t1=fmin(t1,1.0);
				t2=fmax(t2,0.0);
				nxt1=get(r_t_p(Ar+V*t1));
				nxt2=get(r_t_p(Ar+V*t2));
				ans=max(ans,max(nxt1,nxt2));
				t=(nxt1>nxt2?t1:t2);
				stp*=0.95;
			}
		}
		printf("%.4lf\n",ans);
	}
	return 0;
}

比赛时打的60分暴力：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))
#define pi (3.14159265358979323846)
#define eps (1e-10)

template <typename _Tp> inline _Tp read(_Tp&x){
	rg char c11=getchar(),ob=0;x=0;
	while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=1;
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

inline double get(double a,double r){
	double f,p,q,t;
	int h=(int)((int)(a)/60);
	f=a/60-(double)h;
	p=1-(r/100.0);
	q=1-f*(r/100.0);
	t=1-(1-f)*(r/100.0);
	double R,G,B;
	switch(h){
		case 0:R=1,G=t,B=p;break;
		case 1:R=q,G=1,B=p;break;
		case 2:R=p,G=1,B=t;break;
		case 3:R=p,G=q,B=1;break;
		case 4:R=t,G=p,B=1;break;
		case 5:R=1,G=p,B=q;break;
	}
	return R*0.30+G*0.59+B*0.11;
}

int main(){
	double a1,r1,a2,r2;
	int T;read(T);while(T--){
		scanf("%lf%lf%lf%lf",&a1,&r1,&a2,&r2);
		double ans=0.0;
		double x1=r1*cos(a1*pi/180.0);
		double x2=r2*cos(a2*pi/180.0);
		double y1=r1*sin(a1*pi/180.0);
		double y2=r2*sin(a2*pi/180.0);
		double xx=x1,yy=y1,dx=(x2-x1)/100000.0,dy=(y2-y1)/100000.0;
		for(;((xx-x1<eps&&xx-x2>-eps)||(xx-x2<eps&&xx-x1>-eps))&&
			  ((yy-y1<eps&&yy-y2>-eps)||(yy-y2<eps&&yy-y1>-eps))
		;xx+=dx,yy+=dy){
			double X;
			double Y=sqrt(xx*xx+yy*yy);
			if(yy>eps) X=acos(xx/Y)*180.0/pi;
			else X=360.0-acos(xx/Y)*180.0/pi;
			//if(ans<get(X,Y))printf("%lf %lf %lf\n",X,Y,ans);
			ans=fmax(ans,get(X,Y));
			if(dx==0&&dy==0)break;
		}
		printf("%.4lf\n",ans);
	}
	return 0;
}