首页 » 水题 » 正文

贝壳找房性价比


题目链接:https://nanti.jisuanke.com/t/27116

描述

贝壳找房有一个性价比比较的系统,对于两个房源 a,b,a 的价格为 pa 万元,面积 sa 平方米,b 的价格为 pb 万元,面积为 sb 平方米。他们的绝对性价比差定义成为 |pa – pb|/|sa – sb| 。

现在给出 n 个房源的价格和面积,请你求出一对房源使得它们的绝对性价比差最大。

输入格式

输入第一行一个整数 T 表示数据组数。

接下来输入 T 组数据,每一组数据按照下面格式输入。

第一行输入一个整数 n 表示房源的个数。

接下来 n 行,每行输入两个整数 si, pi,分别表示第 i 个房源的面积为 si 平方米,价格为 pi 万元。

数据保证没有任何两个房源的面积和价格都一样。

输出格式

对于每组数据输出一行,如果该组数据的答案趋向于无穷大,输出 −1,否则,输出最大的绝对性价比差。(所有输出误差在 10^-6以内都可以被接受)。

本题答案不唯一,符合要求的答案均正确

样例输入

2
4
1 3
4 5
7 8
3 6
2
4 10
4 11

样例输出

1.500000
-1

题目来源
2018 计蒜之道 初赛 第三场

思路

将si作为x,pi作为y,所有点所能组成的最大斜率了,而最大斜率一定是x坐标相邻的两个点的斜率。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 110000 
using namespace std;  
struct Node{
    int x, y;  
}node[MAXN];

bool cmp(Node a, Node b){
    return a.x<b.x;  
}
int main(){
    //freopen("1.txt", "r", stdin);  
    int T;  
    scanf("%d", &T);  
    while(T--){
        int n;  
        scanf("%d", &n);  
        for(int i=1;i<=n;i++){
            scanf("%d%d", &node[i].x, &node[i].y);  
        }
        sort(node+1,node+1+n,cmp);  //按x的大小排序
        double ans = 0;  
        for(int i=2;i<=n;i++){
            double num = double(node[i].y-node[i-1].y)/double(node[i].x-node[i-1].x);  
            if(num < 0)num=-num;  //注意题目绝对值了
            if(num > ans){
                ans = num;  
            }
        }
        if(ans > 1e8)printf("-1\n");//设置一个很大的数作为是否无穷大
        else printf("%.6lf\n",ans);  
    }
} 

发表评论