2018计蒜之道 第三场 A

2018计蒜之道 第三场 A

题目链接

题意：看到题目上给的公式，自然想到斜率，相当于n个点（Si, Pi）求两个点的最大斜率

思路：把所有点按x轴排序（也就是Si），然后相邻两点算斜率，最后取个MAX就OK了

PS：题目要求斜率无限大时输出-1，所以Si相同时break就好

#include<algorithm>
#include<typeinfo>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<stdio.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
#define pi acos(-1)
#define mod 998244353
ll gcd(ll x, ll y) { return x ? gcd(y%x, x) : y; }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }struct X { double s, p; };
X poi[100005];
double t, n, ans;
int cmp(X a, X b) { return a.s > b.s; }int main() {ios::sync_with_stdio(false);//cin.tie(0);cout << fixed << setprecision(6);while (~scanf("%lf",&t)) while (t--) {scanf("%lf", &n);for (int a = 0; a < n; a++)scanf("%lf%lf", &poi[a].s, &poi[a].p);sort(poi, poi + int(n), cmp);ans = 0;for (int a = 1; a < n; a++) {if (poi[a - 1].s == poi[a].s) {ans = -1;break;}ans = max(ans, fabs((poi[a].p - poi[a - 1].p) / (poi[a].s - poi[a - 1].s)));}printf("%.8lfn", ans);}return 0;
}