P3217 [HNOI2011]数矩形

    • 176通过
    • 689提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 排序 枚举,暴力 计算几何 2011 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    最近某歌手在研究自己的全球巡回演出计划,他将所有心仪的城市都用平面上的一个点来表示,并打算从中挑选出 4 个城市作为这次巡回演出的地点。

    为了显示自己与众不同,他要求存在一个矩形使得挑选出的 4 个点恰好是这个矩形的 4 个顶点,并且希望这个矩形的面积最大。

    这可急坏了其经纪人,于是他向全球歌迷征集方案,当然你这位歌迷一定不会错过这个机会。

    输入输出格式

    输入格式:

    从文件input.txt中读入数据,输入文件的第一行是一个正整数$N$,表示平面上点的个数(即某歌手心仪的城市数)。接下来的$N$行,每行是由空格隔开的两个整数$X_i$和$Y_i$,表示其对应点的坐标。20%的数据满足$N\leq 500$,100%的数据满足$N\leq 1500$,$-10^8\leq X_i,Y_i\leq 10^8$,且输入数据保证答案存在。

    输出格式:

    输出文件 output.txt 仅包含一个非负整数,表示最大的矩形面积。

    输入输出样例

    输入样例#1: 复制
    8
    -2 3
    -2 -1
    0 3
    0 -1
    1 -1
    2 1 
    -3 1 
    -2 1
    
    输出样例#1: 复制
    10
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。