[日常摸鱼]bzoj1038 [ZJOI2008]瞭望塔-模拟退火/几何

题意：给一条平面内$n$个点的折线，要求在折线上搞一个高度$h$的瞭望塔，能够看见折线上所有的点，求$h$的最小值（$n leq 300$）

updata2018.1.21

正解半平面交在另一篇里面…

updata2018.1.5

我发现这题可以随便乱搞过掉…（雾

把所有折线段的$n$条直线求出来，求他们两两之间的交点（这些交点也包括了折线上的折点）和两端的横坐标丢到一个数组$q[]$

答案的横坐标一定在$q[]$里（如果答案在某两个之间的话一定不会更优）

时间复杂度$O(n^3)$…相当暴力

INF不要开小…啧啧啧

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

const int N=305;
struct line
{
    double k,b;
    line(){}
    void calc(double x1,double y1,double x2,double y2)
    {
        k=(y1-y2)/(x1-x2);
        b=y1-k*x1;
    }
    double f(double x)
    {
        return k*x+b;
    }
}ls[N];
int n,tot;
double xs[N],ys[N],q[N*N],ans;
inline double high(double x)
{
    double res=0;
    for(register int i=1;i<n;i++)res=max(res,ls[i].f(x));
    return res;
}
inline double f(double x)
{
    for(register int i=1;i<n;i++)if(xs[i]<=x&&x<=xs[i+1])return ls[i].f(x);
    return 0;
}
int main()
{
    scanf("%d",&n);ans=1e11;
    for(register int i=1;i<=n;i++)scanf("%lf",&xs[i]);
    for(register int i=1;i<=n;i++)scanf("%lf",&ys[i]);
    for(register int i=1;i<n;i++)ls[i].calc(xs[i],ys[i],xs[i+1],ys[i+1]);
    for(register int i=1;i<n;i++)
    {
        for(register int j=i+1;j<n;j++)if(ls[i].k!=ls[j].k)
        {
            double x=(ls[j].b-ls[i].b)/(ls[i].k-ls[j].k);
            if(xs[1]<=x&&x<=xs[n])q[++tot]=x;
        }
    }q[++tot]=xs[1];q[++tot]=xs[n];
    for(register int i=1;i<=tot;i++)if(q[i]!=q[i-1])
    {
        double cur=fabs(high(q[i])-f(q[i]));
        ans=min(ans,cur);
    }printf("%.3lf",ans);
    return 0;
}

View Code

跑得比之前写的不知道快到哪里去了

原文

听说正解平面半交，我不会啊做怎么办，Po姐教你模拟退火搞233

模拟退火随机横坐标，在纵坐标上二分高度

T_T然后注意细节不要写挂

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=305;
struct point
{
    double x,y;
    point(){}
    point(double tx,double ty)
    {
        x=tx;y=ty;
    }
}ps[N];
inline point operator -(point a,point b)
{
    return point(a.x-b.x,a.y-b.y);
}
struct line
{
    point p1,p2;
    double k,b;
    void calc()
    {
        point p=p1-p2;
        k=p.y/p.x;
        b=p2.y-k*p2.x;
    }
}ls[N];
int n;
double now,ansx,ansy;

inline double Rand()
{
    return (rand()%1000)/1000.0;
}
inline double f(line l,double x)
{
    return l.k*x+l.b;
}
inline double f(double x)
{
    for(register int i=2;i<=n;i++)
        if(ls[i].p1.x<=x&&x<=ls[i].p2.x)return f(ls[i],x);
    return 0;
}
inline double operator * (point p1,point p2)
{
    return p1.x*p2.y-p1.y*p2.x;
}
inline bool judge(double x,double mid)
{
    point p(x,mid);
    for(register int i=2;i<=n;i++)
        if((ps[i-1]-p)*(ps[i]-p)<0)
            return 0;
    return 1;
}
inline double check(double x)
{
    double temp,l,r,mid;
    temp=f(x);l=temp;r=1e11;
    while(r-l>(1e-7))
    {
        mid=(l+r)/2;
        if(judge(x,mid))r=mid;
        else l=mid;
    }
    mid-=temp;
    if(mid<ansy)ansx=x,ansy=mid;
    return mid;
}
inline void SA()
{
    double t=ps[n].x-ps[1].x;
    while(t>(1e-5))
    {
        double temp=now+t*(Rand()*2-1);
        if(temp<ps[1].x||temp>ps[n].x)continue;
        double dE=check(now)-check(temp);
        if(dE>0||exp(dE/t)>Rand())
            now=temp;
        t*=0.99;
    }
    t*=10;
    for(register int i=1;i<=1000;i++,t*=0.99)
    {
        double temp=ansx+t*(Rand()*2-1);
        if(temp<ps[1].x||temp>ps[n].x)continue;
        check(temp);
    }
}
int main()
{
    //freopen("input.in","r",stdin);
    //srand(19260817);
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%lf",&ps[i].x);
    for(register int i=1;i<=n;i++)scanf("%lf",&ps[i].y);
    for(register int i=2;i<=n;i++)ls[i].p1=ps[i-1],ls[i].p2=ps[i],ls[i].calc();
    ansy=1e11;ansx=now=(ps[n].x-ps[1].x)/2;SA();
    printf("%.3lf",ansy+(1e-7));
    return 0;
}

View Code

等学了平面半交再来更新