题解 P4636 【[SHOI2011]直线拟合】

· · 题解

我怕不是个傻子

一道模版题肝模拟退火。

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

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

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

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

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

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

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

#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;
}