CF1012A.Photo of The Sky
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Pavel made a photo of his favourite stars in the sky. His camera takes a photo of all points of the sky that belong to some rectangle with sides parallel to the coordinate axes.
Strictly speaking, it makes a photo of all points with coordinates (x,y), such that x1≤x≤x2 and y1≤y≤y2, where (x1,y1) and (x2,y2) are coordinates of the left bottom and the right top corners of the rectangle being photographed. The area of this rectangle can be zero.
After taking the photo, Pavel wrote down coordinates of n of his favourite stars which appeared in the photo. These points are not necessarily distinct, there can be multiple stars in the same point of the sky.
Pavel has lost his camera recently and wants to buy a similar one. Specifically, he wants to know the dimensions of the photo he took earlier. Unfortunately, the photo is also lost. His notes are also of not much help; numbers are written in random order all over his notepad, so it's impossible to tell which numbers specify coordinates of which points.
Pavel asked you to help him to determine what are the possible dimensions of the photo according to his notes. As there are multiple possible answers, find the dimensions with the minimal possible area of the rectangle.
帕维尔拍摄了他最喜欢的星空照片。他的相机可以拍摄天空中所有位于某个与坐标轴平行的矩形区域内的点。
严格来说,该相机拍摄的是所有满足坐标 (x,y) 的点,使得 x1≤x≤x2 且 y1≤y≤y2,其中 (x1,y1) 和 (x2,y2) 分别是所拍摄矩形的左下角和右上角顶点坐标。该矩形的面积可以为零。
拍摄完成后,帕维尔记录下了照片中出现的 n 颗他最喜欢的恒星的坐标。这些点不一定互不相同;天空中的同一位置可能有多颗恒星。
最近帕维尔丢失了他的相机,想购买一台类似的。具体而言,他想知道之前所拍照片的尺寸(即矩形区域的大小)。不幸的是,这张照片也已丢失。他的笔记也帮不上太大忙:笔记本上数字杂乱无章地写得到处都是,因此无法判断哪些数字对应哪些点的坐标。
帕维尔请你帮他根据这些笔记推断出照片可能的尺寸。由于可能存在多种答案,请找出所有可能中矩形面积最小的那组尺寸。
输入格式
The first line of the input contains an only integer n (1≤n≤100000), the number of points in Pavel's records.
The second line contains 2⋅n integers a1, a2, ..., a2⋅n (1≤ai≤109), coordinates, written by Pavel in some order.
输入的第一行包含一个整数 n(1≤n≤100000),表示 Pavel 记录中的点的数量。
第二行包含 2⋅n 个整数 a1, a2, ..., a2⋅n(1≤ai≤109),这些是 Pavel 以某种顺序记录的坐标。
输出格式
Print the only integer, the minimal area of the rectangle which could have contained all points from Pavel's records.
输出唯一的整数,即能够包含 Pavel 记录中所有点的矩形的最小面积。
输入输出样例
输入#1
4 4 1 3 2 3 2 1 3
输出#1
1
输入#2
3 5 8 5 5 7 5
输出#2
0
说明/提示
In the first sample stars in Pavel's records can be (1,3), (1,3), (2,3), (2,4). In this case, the minimal area of the rectangle, which contains all these points is 1 (rectangle with corners at (1,3) and (2,4)).
在第一个样例中,帕维尔记录中的恒星坐标可以是 (1,3)、(1,3)、(2,3)、(2,4)。此时,包含所有这些点的矩形的最小面积为 1(该矩形的两个对角顶点为 (1,3) 和 (2,4))。
输入解题思路,AI测评打分。不知道怎么写?