На плоскости нарисован прямоугольник с противоположными углами в \((0, 0)\) и \((w, h)\) и сторонами, параллельными осям координат.
Задан список из точек на плоскости таких, что каждая точка лежит на стороне прямоугольника, но не в его углу. Также на каждой стороне прямоугольника лежит не менее двух точек.
Ваша задача — выбрать три точки таким образом, что:
- ровно две из них лежат на одной и той же стороне прямоугольника;
- площадь треугольника, построенного на них, максимально возможна.
Выведите удвоенную площадь этого треугольника. Можно показать, что удвоенная площадь треугольника, построенного на точках с целочисленными координатами, всегда целая.
Выходные данные
На каждый набор входных данных выведите одно целое число — удвоенную максимальную площадь треугольника, образованного такими тремя точками, что ровно две из них лежат на одной и той же стороне.
Примечание
Точки в первом наборе входных данных в примере:
- \((1, 0)\), \((2, 0)\);
- \((2, 8)\), \((3, 8)\), \((4, 8)\);
- \((0, 1)\), \((0, 4)\), \((0, 6)\);
- \((5, 4)\), \((5, 5)\).
Наибольший треугольник образон точками \((0, 1)\), \((0, 6)\) и \((5, 4)\) — его площадь равна \(\frac{25}{2}\). Поэтому удвоенная площадь равна \(25\). Две точки на одной стороне: \((0, 1)\) и \((0, 6)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 8
2 1 2
3 2 3 4
3 1 4 6
2 4 5
10 7
2 3 9
2 1 7
3 1 3 4
3 4 5 6
11 5
3 1 6 8
3 3 6 8
3 1 3 4
2 2 4
|
25
42
35
|