题解 P1663 【山】

Riven_Yasuo

2017-09-24 13:12:09

Solution

楼下都是二分,我来水一发数学方法 一次函数初二就学了。 首先求出相邻两个点构成的直线的解析式, 然后枚举,求出每两条斜率一正一负的直线的交点 时间复杂度O(n²)(n<=50) 对交点取最大值即可 AC代码: ```cpp #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; } ```