← 返回题目列表

Codeforces · 1252/H

H. 双子楼

中文机器翻译题面 查看原题

您可能已经知道,空间一直是 ICPC 雅加达的一个问题。为了应对这一问题,ICPC 雅加达计划建造两座新大楼。这些建筑物的形状应为相同大小的矩形。现在,他们的问题是找到土地来建造建筑物。

有 $$$N$$$ 土地可供出售。 $$$i^{th}$$$ 土地呈矩形,大小为 $$$L_i \times W_i$$$。为了获得良好的风水,建筑物的侧面应与土地的侧面平行。

一种方法是在两块不同的土地上建造两座建筑物,每块土地上建造一座(不一定具有相同的方向)。当且仅当至少满足以下条件之一时,才能在 $$$i^{th}$$$ 土地上建造规模为 $$$A \times B$$$ 的建筑物:

- $$$A \le L_i$$$ 和 $$$B \le W_i$$$,或
- $$$A \le W_i$$$ 和 $$$B \le L_i$$$。

- $$$A \times 2 \le L_i$$$ 和 $$$B \le W_i$$$,或
- $$$A \times 2 \le W_i$$$ 和 $$$B \le L_i$$$,或
- $$$A \le L_i$$$ 和 $$$B \times 2 \le W_i$$$,或
- $$$A \le W_i$$$ 和 $$$B \times 2 \le L_i$$$。

您在此问题中的任务是帮助 ICPC Jakarta 找出在 $$$N$$$ 可用土地上他们可以建造的最大建筑物。请注意,ICPC 雅加达必须建造两栋 $$$A \times B$$$ 的建筑物;输出 $$$A \times B$$$ 的最大可能值。

输入

输入以包含整数的行开头: $$$N$$$ ($$$1 \le N \le 100\,000$$$) 表示可用土地的数量。接下来的 $$$N$$$ 行每行包含两个整数: $$$L_i$$$ $$$W_i$$$ ($$$1 \le L_i, W_i \le 10^9$$$) 表示土地的大小。

输出

在一行中输出一个数字,代表 ICPC Jakarta 可以建造的最大建筑物,精确到一位小数(为清楚起见,请参阅示例输入/输出)。

示例

输入 #1

2
5 5
3 4

输出 #1

12.5

输入 #2

2
2 5
4 3

输出 #2

8.0

输入 #3

3
10 1
9 8
7 6

输出 #3

42.0

注意

示例输入/输出 #1 的说明

在第一块土地上可以建造两栋 $$$2.5 \times 5$$$ 的建筑物。

示例输入/输出#2 的说明

在第一块土地和第二块土地上可以分别建造两栋 $$$2 \times 4$$$ 的建筑物。

示例输入/输出 #3 的说明

在第二块和第三块土地上可以分别建造两栋 $$$7 \times 6$$$ 的建筑物。