美文网首页
笔试刷题-百度2018-06-23

笔试刷题-百度2018-06-23

作者: Dodo159753 | 来源:发表于2018-06-23 08:21 被阅读0次

题目描述:


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

输出描述:
一行输出最小面积

输入例子1:
2
0 0
0 3

输出例子1:
9
*/

思路如下:

题目由于要求了正方形的边都要平行于x 、y轴
那么正方形的最小边长为max(maxX-minX, maxY-minY)

代码如下:


#include<stdio.h>
#include<iostream>
#include<climits>
#include<algorithm>

#define MAX_N 1005

using namespace std;

int x[MAX_N], y[MAX_N];

//找最大间隔时间复杂度是O(n)只需要记录之前一段的两个端点并更新就可以了
//排序复杂度O(nlgn)
//直接穷举O(n^2)
int main()
{
    int n;
    while(scanf("%d", &n)==1)
    {
        int max_dx=INT_MIN, max_dy=INT_MIN;
        for(int i=0; i<n; i++)
            scanf("%d%d", x+i, y+i);
        sort(x, x+n);
        sort(y, y+n);
        max_dx=x[n-1]-x[0];
        max_dy=y[n-1]-y[0];
        int d=max(max_dx, max_dy);
        long long s=(long long)d*(long long)d;
        printf("%lld\n", s);
    }
    return 0;
}


相关文章

  • 笔试刷题-百度2018-06-23

    题目描述: 思路如下: 题目由于要求了正方形的边都要平行于x 、y轴那么正方形的最小边长为max(maxX-min...

  • 笔试刷题笔记

    C++中运算符重载是多态性的一种表现 运算符重载是针对C++原有运算符进行的,不可能通过重载创造出新的运算符 除了...

  • 公考经验五

    第九篇 笔试阶段。总体说下,笔试备考主要是刷题和一直写申论。行测下载粉笔公考APP去刷题,界面很简洁,题目解释也很...

  • 笔试算法刷题

    原创:王稳钺资料来源:安老师 一、刷题方法与面\笔试能力突破技巧 平时刷题时,市面上大多数尤其以LeetCode为...

  • 腾讯市场策划与推广 笔试+面试

    腾讯笔试+面试 面试岗位 市场策划与推广 笔试篇 腾讯的笔试刷人不多。笔试会先找时间有一轮模拟笔试让你熟悉环境和题...

  • 笔试刷题-百度2018-06-04

    题目描述: 思路如下: 直接bf模拟 采用模拟的方式计数即可,没一个节点有一个idx val, 其实就是一旦发现 ...

  • 笔试刷题-百度2018-06-21

    题目描述: 思路如下: K个小于好把n给数分成了k+1个降序序列descSeq1 descSeq2 ... des...

  • 笔试刷题-百度2018-06-17

    题目描述: 思路如下: 维护3个指针即可 代码如下:

  • 笔试刷题-百度2018-06-20

    题目描述: 思路如下: 第一次把第二小放到最后第二次把第三小放到最后以此类推即可先把Node按照val排序,若va...

  • 笔试刷题-百度2018-06-24

    题目描述: 思路如下: 设pss为ss一分钟内能吊到鱼概率,根据题意由于其随机一个钓鱼,那么其吊到鱼概率为概率矩阵...

网友评论

      本文标题:笔试刷题-百度2018-06-23

      本文链接:https://www.haomeiwen.com/subject/hhhryftx.html