登山(mountain)
【题目描述】
为了开发旅游项目，*市决定建立登山栈道，栈道都是从一个山顶建到另一个山顶。为了简化问题我们假设所有的山顶都在同一条直线上。为了评估建设栈道的难度，委员会决定计算出最抖的栈道的倾斜度。委员会将所有的山顶画在了一个平面直角坐标系中。对于两个山顶（x1,y1）,(x2,y2)之间的栈道定义倾斜度为(y2-y1)/(x2-x1).请帮忙计算出倾斜度最大的山顶之间的倾斜度【输入格式】
第一行一个整数 n 表示山顶的数量接下来 n 行每行两个整数表示每个山顶的坐标
输入数据保证 n<=100000 坐标的绝对值小于 10000000
【输出格式】
一个实数表示最大的倾斜度，精确到小数点后 5 位。本题采取实数比较的方式判定答案的正确性
【样例输入】
3
1 1
2 3
3 4
【样例输出】
2.00000
【样例解释】
1,2 两座之间的倾斜度为(3-1)/(2-1) = 2 1,3 两座之间的倾斜度为（4-1）/（3-1）=1.5 2,3 两座之间的倾斜度为（4-3）/（3-2） = 1
所以答案为 2.00000
【子任务】
对于 60%的数据 n<=1000
解析：60分可以直接暴力枚举任意两个，但正解：
按x排序，然后相邻两个才可能是最大的，具体证明用几何的方法
代码（60）
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100005
#define db double
db ans;
int n;
int x[MAXN],y[MAXN];
db xl;
int main()
{
//freopen("mountain.in","r",stdin);
//freopen("mountain.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
{
scanf("%d%d",&x[i],&y[i]);
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i != j)
{
xl = (db(y[i]-y[j]))/((db(x[i]-x[j])));
//printf("%d %d %.2lf\n",i,j,xl);
if(xl > ans)
ans = xl;
}
printf("%.5lf",ans);
return 0;
}
/*
3
1 1
2 3
3 4
*/
100分：
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define DB double
struct ding//山顶
{
int x,y;
}a[MAXN];
DB ans = -1000000000;
DB xl;//斜率
int n;
bool cmp(ding x,ding y)
{
return x.x < y.x;
}
void rd()//输入
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
}
int main()
{
rd();
for(int i = 1; i < n ; i ++)
{
xl = DB(a[i].y - a[i+1].y)/DB(a[i].x - a[i+1].x);
if(xl > ans)
ans = xl;
}
printf("%.5f",ans);
return 0;
}
/*
3
1 1
2 3
3 4
*/
原文：http://www.cnblogs.com/lahlch/p/7637403.html