P1663 山 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 赵海鲲
    请问 为什么要这样读入
  • 13874066251ly
    捕捉初二CTSC金牌
  • sel_fish
    有图好评
作者: Manjusaka丶梦寒 更新时间: 2018-09-20 19:55  在Ta的博客查看 举报    10  

只能说这是一道数学题,似乎并没有蓝题那么难。

当我们第一眼度完题的时候,很显然我们要找到所有直线相交的最高点。

幸运的是$n \le 5000 $,我们计算出每一条直线的解析式来以后$n^2$枚举就好了,题解中也有这种做法的解答,就不详细说了,我们考虑要是数据再大一点呢? 我们考虑二分答案,毕竟$n \times n$和$n \times logn$那完全就是两个概念啊。

求直线的解析式应该初中就学了吧,为了避免某些人没学还是稍微提一下吧(大佬可直接跳过)。 此处输入图片的描述

对于这直线来说,首先第一==定义函数解析式为$y=ax+b$ 斜率$a$,为$(y1-y2)/(x1-x2)$,有了斜率我们要求b的值,我们将斜率带入直线上某个点带入$(x_1,y_1)$,那么$$y=ax+b=>y_1=ax_1+b=>b=y_1-ax_1$$ 这就求出了一条直线函数解析式。 接下来我们就可以枚举答案了,高度左边缘为$0$,右边缘最大为$1000000$.

最重要的就是$check()$函数啦。 对于每个函数值得判断我们要确定这条直线在哪个区间范围内满足可以被看见(函数值小于判断的值)。 还是看图吧,假设现在判断答案c是否合法。 对于斜率小于0的直线来说 此处输入图片的描述

我们找到$y=c$这条直线与直线的交点$x$,那么对于任意大于$x$的点都是看一由$c$照亮的,那么我们对于斜率小于0的每一条直线记录一个合法的最大左边界$L$(因为要满足所有直线)。

同理对于斜率大于0的直线,求一个最小的右端点$R$。

对于斜率等于0的直线只需要判断b是否小于c就好了。 当$L \le R$是答案合理。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
int n;
double x[5006],y[5006],a[5006],b[5006],ans;
bool check(double x)
{
    double L=-2e9,R=2e9;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<0)L=max(L,(x-b[i])/a[i]);
        else if(a[i]>0)R=min(R,(x-b[i])/a[i]);
        else if(x<b[i])return 0;
    }
    return L<=R;
}
int main()
{
    scanf("%d%lf%lf",&n,&x[1],&y[1]);
    for(int i=2;i<=n;i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
        a[i]=(y[i]-y[i-1])/(x[i]-x[i-1]);
        b[i]=y[i]-a[i]*x[i];
    }
    double l=0,r=1000000;
    while(l<=r)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid-0.0001,ans=mid;
        else l=mid+0.0001;
    }
    printf("%.2lf",ans);
}

鄙人不才,有错误请指出,喜欢就点个赞吧。

评论

  • 13874066251ly
    顶上去
  • 13874066251ly
    大佬
作者: iyanhang 更新时间: 2018-04-13 22:55  在Ta的博客查看 举报    6  

楼上题解里有纯数学的办法,这里提供一下普遍的二分答案的办法。

具体:

  • 求出直线的斜率,截距等资料。
  • 二分枚举高度y。
  • check(mid)函数:如果对于任意一条直线,存在(x,y)在直线的上端或在直线上则true.
  • 判断时,通过直线方程求出满足y的点(x0,y),
    1. 对于k>0,则x的解集的右端点取x0.
    2. 对于k<0,则左端点取x0.
    3. 对于k==0,直接看b和mid的关系.
  • 最后(l,+inf)...(-inf,r)等等取交集,即判断return l<=r即可。
#include <bits/stdc++.h>
using namespace std;
const int MN=5005;
typedef long long ll;

struct line
{
    double k,b;
    int x1,y1,x2,y2;
    void solve()
    {
        k=((double)(y2-y1))/((double)(x2-x1));
        b=(double)y2-k*(double)x2;
    }
}l[MN];
/*double cross(line l1,line l2)
{
    if (l1.k==l2.k) return 0.00;
    return (l1.b*l2.k-l2.b*l1.k)/(l2.k-l1.k);
}*/
int n;
bool check(double x)
{
    double L=-2e9,R=2e9;
    for (int i=1;i<n;++i)
    {
        if (l[i].k<0) L=max(L,(x-l[i].b)/l[i].k);
        else if (l[i].k>0) R=min(R,(x-l[i].b)/l[i].k);
        else if (x<l[i].b) return false;
    }
    return L<=R;
}
ll read(){
    ll f=1,x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    n=read();
    int x1,y1,x2,y2;x1=read();y1=read();
    for (int i=2;i<=n;++i)
    {
        x2=read();y2=read();
        l[i-1].x1=x1,l[i-1].y1=y1,l[i-1].x2=x2,l[i-1].y2=y2;
        l[i-1].solve();
        x1=x2,y1=y2;
    }
    double L=0.00,R=2e9;
    while (L+0.001<=R)
    {
        double mid=(L+R)/2.00;
        if (!check(mid)) L=mid; //don't need to plus 1.
        else R=mid;
    }
    printf("%.2lf",R);
    return 0;
}

评论

  • zmxqs
    freopen拿来坑人的吗
  • 浅爱
    那叫防抄袭
作者: Justin_N_Wu 更新时间: 2017-05-03 17:34  在Ta的博客查看 举报    4  

如果我们把相邻的两个点连接起来,看作一条条直线,那么我们可以发现我们要求的就是找到一个点,使它在每一条的直线的上方或在直线上,并且要求y坐标越小越好。

首先第一步当然是这n-1条直线的表达式给求出来(别说不会,初二就学过了好吧?)

然后我们会发现,对于我们枚举的每一个高度,对于每一条直线都有一个满足要求的区间,那么我们怎么判断这个高度是否可行?显然,若这些区间有交集的话,那么就是有解了,否则就是不行。

枚举高度我们可以通过二分来实现,剩下就是解一下不等式问题就可以了。

代码如下:

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5005;
struct ad{ int x,y; } a[maxn];
struct line{ double k,b; } b[maxn];   //存直线的表达式
int n; double l,r,mid,L,R,ans;
inline int read(){
    int ret=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
inline bool check(double x){
    L=-2e9,R=2e9;
    for (int i=1;i<n;i++){
        if (b[i].k<0) L=max(L,(x-b[i].b)/b[i].k);    //由于k可能小于0,注意不等式两边同除以负数要变号
        if (b[i].k>0) R=min(R,(x-b[i].b)/b[i].k);
        if (b[i].k==0&&b[i].b>x) return 0;    //k等于0的话一除就暴了,注意特判
    }
    return L<=R;
}
int main(){
    freopen("hill.in","r",stdin);
    freopen("hill.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    for (int i=1;i<n;i++){
        b[i].k=1.0*(a[i].y-a[i+1].y)/(a[i].x-a[i+1].x);      //自己推一下的话,应该能懂
        b[i].b=1.0*a[i].y-b[i].k*a[i].x;
    }
    l=0,r=1000000;
    while (r-l>=0.001){    //二分小数的办法
        mid=(l+r)/2.0;
        if (check(mid)) ans=r=mid; else l=mid;
    }
    printf("%.2lf\n",ans);
    return 0;
}

PS 本人第一次写题解,多多见谅

评论

  • liuziming
    直接万能头就行了
作者: Riven_Yasuo 更新时间: 2017-09-24 13:12  在Ta的博客查看 举报    2  

楼下都是二分,我来水一发数学方法

一次函数初二就学了。

首先求出相邻两个点构成的直线的解析式,

然后枚举,求出每两条斜率一正一负的直线的交点

时间复杂度O(n²)(n<=50)

对交点取最大值即可

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define Close fclose(stdin);fclose(stdout);
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define dop(i,m,n) for(int i=m;i>=n;i--)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 2147483647
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<='0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int maxn=5050;
double x[maxn],y[maxn],a[maxn],k[maxn],ans;
int n;
int main(){
    scanf("%d%lf%lf",&n,&x[1],&y[1]);
    rep(i,2,n){
       scanf("%lf%lf",&x[i],&y[i]);
       a[i]=(y[i]-y[i-1])/(x[i]-x[i-1]);  //y=ax+k
       k[i]=y[i]-a[i]*x[i];        //求出直线解析式
    }
    rep(i,2,n)
       rep(j,i+1,n)
          if(((a[j]>0&&a[i]<0)||(a[j]<0&&a[i]>0))){    //如果两条直线斜率一正一负
            double X=(k[i]-k[j])/(a[j]-a[i]);                  //求出交点X坐标
            if(ans<X*a[i]+k[i])                                  //ans对交点Y坐标取最大值
              ans=X*a[i]+k[i];
          }
          else if(!a[j]&&!a[i]&&k[i]==k[j])        //特判,常函数
            if(ans<k[i])
              ans=k[i];
    printf("%.6lf",ans);    //保留6位小数
    return 0;
}

评论

  • 还没有评论
作者: Delva 更新时间: 2018-10-18 07:59  在Ta的博客查看 举报    1  

题意很好懂,由于有x[i+1]>x[i]的保证,可以转化为找到一个最低点在所有直线上方。用$f_i(x)$表示点i和点i+1联立的直线,不难发现,所有直线的上方交集$ y>=f_i(x)$的边界$max$ { $f_i(x)$ }为一个下凸函数,我们要找的即是函数最低点。通过三分法求极值,便能得到最低点。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
template<class T>inline void read(T &aa) {
  int k=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
  for(;isdigit(c);c=getchar()) k=(k<<3)+(k<<1)+(c-'0');aa=k*f;
}
const int maxn = 5010;
const double eps = 1e-8;
struct P{P(){}double x,y;}A[maxn];
int n;
double getY(double x0){//获得横坐标为x0时放灯的最低点 
    double res = 0.0;
    for(int i=1;i<n;++i){
        res=max(res,A[i].y+(x0-A[i].x)*(A[i].y-A[i+1].y)/(A[i].x-A[i+1].x));//联立点i与点i+1得到下凸函数的值
    }return res;
}
int main(void){
    read(n);
    for(int i=1;i!=n+1;++i)scanf("%lf%lf",&A[i].x,&A[i].y);
    //三分法求极值(保证极值始终在l与r之间,通过比较m1和m2缩小范围) 
    double l=0.0,r=100000.0;
    while(abs(l-r)>eps){
        double m1 = (l+l+r)/3,m2 = (l+r+r)/3;
        if(getY(m1)<getY(m2))r=m2;else l=m1;
    }
    printf("%.2lf",getY(l));
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。