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

updata2018.1.21

---

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

updata2018.1.5

---

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

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

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

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

INF不要开小…啧啧啧

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

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

原文

---

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

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

T_T然后注意细节不要写挂

#include
#include
#include
#include
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(1e-5))
{
double temp=now+t*(Rand()*2-1);
if(tempps[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(tempps[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;
}

等学了平面半交再来更新