M. Нужно БОЛЬШЕ шашлыка

Codeforces
IDCF10077M
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
В волшебной стране находится бескрайнее поле. На этом поле растут шашлычки! Из земли в прямом смысле вырастают шампуры с нанизанными кусочками прожаренного на костре мяса. Также в поле находятся N столбов. Владелец поля с шашлыками, Милк Кукис, решил построить себе на своём поле дом (жить на поле с шашлыками… Что ещё для счастья надо?). Для того чтобы построить дом, нужно сначала определиться с его местоположением. Милк Кукис решил, что для удобства стоит натянуть верёвку между четырьмя уже существующими столбами и внутри образовавшегося четырёхугольника построить дом. Он хочет, чтобы территория, выделенная для постройки дома, была максимально приближена к числу K. Для решения этой проблемы Милк Кукис обратился к автору задач и пообещал ему шашлык. Милк Кукис попросил автора задач найти четыре столба, соединив которые, можно получить четырёхугольник (он может быть невыпуклым), площадь которого максимально приближена к числу K, причём Милк Кукису важна лишь площадь полученного четырёхугольника, поэтому он просит узнать именно её. Автор задач съел шашлык, а работу поручил Вам. В первой строке через пробел даны числа N и K (4 ≤ N ≤ 200, 0 < K ≤ 106). N – натуральное число, K – вещественное число, с точностью до 10 - 4. Далее следуют N строк. В i-ой строке указаны два числа xi и yi – координаты i-го столба. Обе координаты каждого столба по модулю не превосходят 500. Гарантируется, что никакие три точки не лежат на одной прямой. В единственной строке выведите число – площадь четырёхугольника - наиболее близкое к числу K. Площадь выводить с точностью до 10 - 4. Если решений несколько, то выведите наибольшее. ## Входные Данные В первой строке через пробел даны числа N и K (4 ≤ N ≤ 200, 0 < K ≤ 106). N – натуральное число, K – вещественное число, с точностью до 10 - 4.Далее следуют N строк. В i-ой строке указаны два числа xi и yi – координаты i-го столба. Обе координаты каждого столба по модулю не превосходят 500. Гарантируется, что никакие три точки не лежат на одной прямой. ## Выходные Данные В единственной строке выведите число – площадь четырёхугольника - наиболее близкое к числу K. Площадь выводить с точностью до 10 - 4. Если решений несколько, то выведите наибольшее. ## Примеры Входные данные6 6.0000 41 24 43 24 00 0Выходные данные6.0000Входные данные6 3.5000 03 24 01 20 44 4Выходные данные4 [samples]
**Definitions** Let $ N \in \mathbb{Z} $, $ 4 \leq N \leq 200 $, be the number of poles. Let $ K \in \mathbb{R} $, $ 0 < K \leq 10^6 $, be the target area. Let $ P = \{ (x_i, y_i) \mid i \in \{1, \dots, N\} \} $ be the set of pole coordinates, with $ |x_i|, |y_i| \leq 500 $, and no three points collinear. **Constraints** - All points in $ P $ are distinct. - No three points are collinear. **Objective** Find the quadrilateral (possibly non-convex) formed by four distinct points from $ P $, whose area $ A $ satisfies: $$ |A - K| \text{ is minimized} $$ If multiple such areas exist, choose the **largest** $ A $. Output the value of $ A $ with precision $ 10^{-4} $.
API Response (JSON)
{
  "problem": {
    "name": "M. Нужно БОЛЬШЕ шашлыка",
    "description": {
      "content": "В волшебной стране находится бескрайнее поле. На этом поле растут шашлычки! Из земли в прямом смысле вырастают шампуры с нанизанными кусочками прожаренного на костре мяса. Также в поле находятся N сто",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10077M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "В волшебной стране находится бескрайнее поле. На этом поле растут шашлычки! Из земли в прямом смысле вырастают шампуры с нанизанными кусочками прожаренного на костре мяса. Также в поле находятся N сто...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 4 \\leq N \\leq 200 $, be the number of poles.  \nLet $ K \\in \\mathbb{R} $, $ 0 < K \\leq 10^6 $, be the target area.  \nLet $ P = \\{ (x_i, y_i) \\mid i \\in \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments