自动搬运

查看原文

来自洛谷，原作者为

	CR_Raphael 童年遗留，好羞耻

搬运于2025-08-24 22:02:10，当前版本为作者最后更新于2019-01-26 20:40:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我怕不是个傻子

一道模版题肝模拟退火。

-孩子沉迷退火怎么办？逼他用模拟退火做计算几何再让他打正解，妈妈再也不用担心我的常数啦！

咳，说正解，旋转卡壳求凸包点边最长值，

不过朕的代码……我一开始想歪了……直接凸包+二分上了……似乎没见过这样搞的……

就是找凸包上每个边斜率在凸包另一侧的位置，就确定了离该边最远的点。其实如果用尺取法做的话，就等价于旋转卡壳了。

所以我独立发明了旋转卡壳？

贴个超级丑的代码，希望正统旋转卡壳亲之信之，则几何之隆，可计日而待也。

懒得做正解了，如果您是初学者，想用这篇代码为蓝本学旋转卡壳，那么我建议换一篇题解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const double pi = 3.1415926535;
const int maxn = 100005;
const double inf = 2000000001;
int n;
double k, l, ans;
int t;

struct pointt {
	double x, y, tk;
} a[maxn], p[maxn];

int findd(double ff) {
	int l, r, mid;
	l=1; r=t;
	while(l < r) {
		mid=(l+r+1)/2;
		if(a[mid].tk <= ff) l=mid;
		else r=mid-1;
	}
	return l;
}

double count_ans(int kx) {
	int i;
	double kk=a[kx].tk, maxx, minn;
	double kt;
	if(kk < pi) kk+=pi;
	else kk-=pi;
	if((a[kx].x!= a[kx-1].x)) kt=(a[kx].y-a[kx-1].y)/(a[kx].x-a[kx-1].x);
	else kt=inf;
	
	i=findd(kk);
	maxx=(kt*a[i].x-a[i].y)/sqrt(kt*kt+1);
	minn=(kt*a[kx].x-a[kx].y)/sqrt(kt*kt+1);
	
	if(kt == inf) {
		maxx=a[i].x;
		minn=a[kx].x;
	}
	return abs(maxx-minn)/2;
}

bool cmp(pointt a1, pointt a2) {
	return a1.tk < a2.tk;
}

double count(pointt a1, pointt a2) {
	double tt=atan2((a1.y-a2.y), (a1.x-a2.x));
	if(tt < 0) tt+=2*pi;
	return tt;
}

double ll(pointt a1, pointt a2) {
	return sqrt((a1.y-a2.y)*(a1.y-a2.y) + (a1.x-a2.x)*(a1.x-a2.x));
}

int main() {
	int i, minp, maxp;
	double miny;
	scanf("%d", &n);
	for(i=1; i <= n; i++) 
		scanf("%lf%lf", &p[i].x, &p[i].y);
	
	miny=p[1].y; minp=1;
	for(i=1; i <= n; i++) {
		if(p[i].y < miny) miny=p[i].y, minp=i;
	}
	swap(p[1], p[minp]);
	for(i=1; i <= n; i++) 
		p[i].tk=atan2(p[i].y-p[1].y, p[i].x-p[1].x);
	sort(p+1, p+1+n, cmp);
	t=0; i=0;
	do {
		i++;
		if(i == n+1) i=1;
		while(t > 1 && (count(p[i], a[t]) < count(a[t], a[t-1]))) {
			t--;
		}
		t++;
		a[t]=p[i];
		a[t].tk=count(a[t], a[t-1]);
	} while(i != 1 || t <= 1);
	
	miny=inf;
	a[1].tk = -0.1;
	for(i=2; i <= t; i++) {
		miny=min(miny, count_ans(i));
	}
	
	printf("%.2lf\n", miny);
	return 0;
}

另外呢，将军退火，性行淑均，适用于昔日，评测机称之曰90，愚以为此做题之法，仅供观赏，诸将切勿惫怠。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;

const int maxn = 100005;
const double maxl = 200000000;
const double pai = 3.14159;
const double delta=0.9;

int n;
double a[maxn], b[maxn], t;
double ansp, ansk;
int ts;

double count(double k) {
    int i;
    double ll, maxx=-maxl, minn=maxl;
    
    for(i=1; i <= n; ++i) {
        ll=k*a[i]-b[i];
        minn=min(minn, ll);
        maxx=max(maxx, ll);
    }
    
    maxx=maxx/sqrt(k*k+1);
    minn=minn/sqrt(k*k+1);
    
    return (maxx-minn)/2;
}

void SA() {
    double kk=ansk;
    double tk, newp;
    t=1777;
    while(t > 1e-14) {
        tk=kk+(rand()*2.0-RAND_MAX)*1.0/10000*t;
        newp=count(tan(tk));
        //cout<<tk<<' '<<newp<<endl;
        //cin>>ts;
        
        if(newp < ansp) {
            kk=tk;
            ansk=tk;
            ansp=newp;
        }
        else if(exp(-(newp-ansp)*1000/t)*RAND_MAX > rand()) {
            kk=tk;
        }
        t*=delta;
    }
    return;
}

int main() {
    srand(time(NULL));
    scanf("%d", &n);
    //cout<<RAND_MAX<<endl;
    int i;
    double pi, tt, stt;
    for(i=1; i <= n; ++i) {
        scanf("%lf%lf", &a[i], &b[i]);
    }
    //cout<<count(1)<<endl;
    
    ansk=0;
    ansp=count(tan(ansk));
    for(pi=-1.6; pi <= 1.6; pi+=0.01) {
        tt=count(tan(pi));
        if(tt < ansp) {
            ansp=tt;
            ansk=pi;
        }
    }
    
    stt=ansk;
    for(pi=stt-0.1; pi <= stt+0.1; pi+=0.001) {
        tt=count(tan(pi));
        if(tt < ansp) {
            ansp=tt;
            ansk=pi;
        }
    }
    
    stt=ansk;
    for(pi=stt-0.01; pi <= stt+0.01; pi+=0.0001) {
        tt=count(tan(pi));
        if(tt < ansp) {
            ansp=tt;
            ansk=pi;
        }
    }
    
    stt=ansk;
    for(pi=stt-0.001; pi <= stt+0.001; pi+=0.00001) {
        tt=count(tan(pi));
        if(tt < ansp) {
            ansp=tt;
            ansk=pi;
        }
    }
    
    SA();
    
    printf("%.2lf\n", ansp);
    return 0;
}