2016百度笔试题

1、裁剪网格纸

题目描述

度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
输入描述:
第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点
输出描述:
一行输出最小面积
输入例子:
2
0 0
0 3

输出例子:
9

题目分析：

只要找出给出的坐标中横坐标和纵坐标的对应的最大值和最小值的差值，取较大的值，进行平方即可。

代码实现：

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
//裁剪网格纸
int GetMinArea(vector<int> x, vector<int> y)
{
    if (x.size() == 0 || y.size() == 0)
        return 0;
    //找出横纵坐标的最大差值
    int diffX = 0;
    int diffY = 0;
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    diffX = x[x.size() - 1] - x[0];
    diffY = y[y.size() - 1] - y[0];
    if (diffX > diffY)
        return diffX*diffX;
    else
        return diffY * diffY;
}
int main()
{
    int n = 0;
    vector<int> x;
    vector<int> y;
    while (cin >> n)
    {
        while (n--)
        {
            int row = 0;
            int col = 0;
            cin >> row >> col;

            x.push_back(row);
            y.push_back(col);
        }
        cout << GetMinArea(x, y) << endl;
        x.clear();
        y.clear();
    }
    return 0;
}

2、钓鱼比赛

题目描述

ss请cc来家里钓鱼，鱼塘可划分为n＊m的格子，每个格子有不同的概率钓上鱼，cc一直在坐标(x,y)的格子钓鱼，而ss每分钟随机钓一个格子。问t分钟后他们谁至少钓到一条鱼的概率大？为多少？
输入描述:
第一行五个整数n,m,x,y,t(1≤n,m,t≤1000,1≤x≤n,1≤y≤m);
接下来为一个n＊m的矩阵，每行m个一位小数，共n行，第i行第j个数代表坐标为(i,j)的格子钓到鱼的概率为p(0≤p≤1)
输出描述:
输出两行。第一行为概率大的人的名字(cc/ss/equal),第二行为这个概率(保留2位小数)
输入例子:
2 2 1 1 1
0.2 0.1
0.1 0.4
输出例子:
equal
0.20

题目分析：

分别计算出ss和cc钓到鱼的概率，进行比较。t分钟钓到至少一个鱼的概率可以这样计算：1-t分钟一只鱼都没有钓到的概率。
格式输出（保留小数点后两位）：
setiosflags(iOS::fixed) ， setprecision(2)

代码实现：

#include<iostream>
using namespace std;
#include <iomanip>
#include<math.h>
void Match(float a[],int n, int m, int x,int y,int t)
{
    float cc = a[(x-1)*m+y-1];
    float ss = 0.0;
    for (int i = 0; i < n*m; ++i)
    {
        ss += a[i];
    }
    ss /= (n*m);
    if (cc > ss)
    {
        cout << "cc" << endl << setiosflags(ios::fixed) << setprecision(2) << 1 - pow(1 - cc, t)<<endl;
    }
    else if (cc == ss)
    {
        cout << "equal" << endl << setiosflags(ios::fixed) << setprecision(2)<<1 - pow(1 - ss, t) <<endl;
    }
    else
    {
        cout << "ss" << endl << setiosflags(ios::fixed) << setprecision(2) <<1 - pow(1 - ss, t)<<endl;
    }
}
int main()
{
    int n = 0, m = 0, x = 0, y = 0,t = 0;
    while (cin >> n >> m >> x >> y >> t)
    {
        float* a = new float[n*m];
        for (int i = 0;i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin>>a[m * i + j];
            }
        }
        Match(a, n,m, x,y,t);
    }
    return 0;
}