题解 P1663 【山】
Riven_Yasuo
2017-09-24 13:12:09
楼下都是二分,我来水一发数学方法
一次函数初二就学了。
首先求出相邻两个点构成的直线的解析式,
然后枚举,求出每两条斜率一正一负的直线的交点
时间复杂度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;
}
```