当前位置:首页 > 枚举 > 正文
洛谷P1959遗址[NOI导刊]
131+

题目大意:平面上有n个点,请找出4个点作为正方形的四个角,找到的正方形最大面积是多少?

题目描述

很久很久以前有一座寺庙,从上往下看寺庙的形状正好是一个正方形,由4个角上竖立的圆柱搭建而成。现在圆柱都倒塌了,只在地上留下圆形的痕迹,可是现在地上有很多这样的痕迹,专家说一定是最大的那个。

写一个程序,给出圆柱的坐标,找出由4个圆柱构成的最大的正方形,因为这就是寺庙的位置,要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。

例如图有l0根柱子,其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形,(1,1),(4,O),(5,3),(2,4)也可以,后者是其中最大的,面积为l0。

输入输出格式

输入格式

第一行包含一个N(1≤N≤3 0 0 0),表示柱子的数量。

接下来N行,每行有两个空格隔开的整数表示柱子的坐标(坐标值在0到5000之间),柱子的位置互不相同。

输出格式

如果存在正方形,输出最大的面积,否则输出0。

输入输出样例

输入样例 #1

 10
 9 4
 4 3
 1 1
 4 2
 2 4
 5 8
 4 0
 5 3
 0 5
 5 2

输出样例 #1

10

说明

【数据范围】

30%满足:1≤N≤100

60%满足:1≤N≤500。

解题思路

枚举正方形相邻的两个点,就可以计算出另外两个点的坐标,如果该坐标存在,那么就可以组成正方形,打擂台记录最大值即可。

举个例子,底边是左下往右上方向的。y增大了cy,那么对应顶边的两个顶点,x会减少cy。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P1959遗址[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter