В этом году главой Флатландии является Егор. Всег...

Question

В этом году главой Флатландии является Егор. Всего во Флатландии проживает людей, каждый в своем доме. i-й дом находится в целочисленной точке (xi, yi).
Егор может выделить некоторые тройки людей. Требуется лишь, чтобы каждый человек относился не более, чем к одной тройке. Тройка людей считается счастливой, если треугольник, образованный их домами, является невырожденным (то есть три дома не находятся на одной прямой).
Помогите Егору определить, какого максимального количества счастливых троек можно добиться во Флатландии.
Формат входных данных
Первая строка содержит число n(3<=n<=300) — количество жителей во Флатландии.
i-я из следующих строчек содержит числа xi и yi (-10^9<=xi, yi<=10^9) — координаты дома, где проживает i-й человек.
Гарантируется, что никакие два дома не находятся в одной точке.
Формат выходных данных
Выведите одно число — максимальное количество счастливых троек, которого можно добиться во Флатландии.
Комментарий к примеру
В примере можно получить две счастливые тройки. Например, подойдет разбиение (1,1), (2,2), (1,4), и (6,3),(4,5), (4,1)
Примеры данных
ввод:
7
1 1
2 2
1 4
6 3
4 5
4 1
3 3
вывод:
2
ответ на языке go

Answer 1

Ниже приведён разбор задачи и пример (достаточно простого) решения на Go.

Идея задачи

У нас есть $n$ точек (дома жителей), и мы хотим «разбить» часть жителей на тройки так, чтобы каждая тройка образовывала невырожденный треугольник (то есть три точки из тройки не лежат на одной прямой). При этом каждый житель может входить не более чем в одну тройку. Нужно найти максимально возможное число таких «счастливых» троек.

Краткий анализ

Верхняя граница очевидна: нельзя получить более $\lfloor n / 3 \rfloor$ троек, так как каждая тройка «занимает» ровно 3 разных человека.
Полный перебор по всем тройкам и затем поиск максимального набора непересекающихся троек (т.,е. решение задачи о максимальном 3- matching в 3-мерном гиперграфе) — задача, в общем случае, нетривиальная и при $n=300$ может быть слишком громоздкой (в худшем случае число троек порядка $O(n^3)$ , что достигает 27 миллионов). Кроме того, классический полный бэктрекинг по этим тройкам тоже может оказаться слишком тяжёлым.
Геометрические факторы:
- Если все $n$ точек коллинеарны (лежат на одной прямой), ответ равен 0.
- Если есть «большая» коллинеарная подмножность, она усложняет формирование троек «мешивать» с точками вне этой прямой.
- При «общем положении» (мало коллинеарностей больших подмножеств) можно заполучить практически $\lfloor n/3 \rfloor$ троек, распределяя точки почти произвольно.
Практический подход для данной задачи (с ограничением $n \le 300$ ) часто сводят к тому, что:
- Проверяют, не все ли точки на одной прямой. Если да — ответ 0.
- Иначе стараются жадно формировать невырожденные тройки и на практике получают оптимум или очень близкий к нему результат.
Небольшая «хитрость» жадного алгоритма: если брать точки в каком-то порядке (скажем, сортируя по $x$ , потом по $y$ ) и на каждом шаге пытаться найти тройку $(i,j,k)$ , которая не коллинеарна, — в большинстве «случайных» конфигураций мы получаем $\lfloor n/3 \rfloor$ .

В «очень плохих» случаях (где действительно много коллинеарных наборов), простой жадный алгоритм порой может не достичь оптимума; однако реализация более «умных» алгоритмов (типа гиперграфового максимального 3-matching) достаточно трудоёмка. Задача (особенно в учебном контексте) обычно подразумевает, что хорошо реализованный жадный/эвристический подход либо достаточен, либо же требуется аккуратный перебор с отсечениями (что тоже возможно, но писать его с нуля сложно).

Ниже приведён упрощённый вариант решения на Go, основанный на жадной идее:

Считаем точки.
Проверяем тривиальный случай: все ли $n$ точек лежат на одной прямой? Если да — отвечаем 0.
Иначе запускаем многократный жадный алгоритм (возможно, с перемешиванием точек) с целью подобрать максимально возможное число троек.
- Для каждой попытки:
  - Идём по списку доступных точек; как только находим тройку $(p, q, r)$ , у которой площадь $\neq 0$ (нет коллинеарности), «забираем» её в решение, исключаем эти три точки из доступных и продолжаем.
- Сохраняем лучший из найденных результатов.
Выводим найденный максимум.

Такой подход (особенно если несколько раз перемешивать точки) на практике неплохо работает для $n \le 300$ и часто укладывается во время. Конечно, при желании можно добавить различные оптимизации (хранить использованность в битсетах, делать быстрые проверки и т.д.).

Ниже — пример кода на языке Go, иллюстрирующего описанный метод.

go
package main

import (
    "bufio"
    "fmt"
    "math/rand"
    "os"
    "time"
)

// Точка на плоскости
type Point struct {
    x, y int64
}

// Проверяем, коллинеарны ли три точки (p1, p2, p3).
// Используем векторное произведение (арны.
func collinear(p1, p2, p3 Point) bool {
    return (p2.x - p1.x)*(p3.y - p1.y) -
           (p2.y - p1.y)*(p3.x - p1.x) == 0
}

// Проверяем, лежат ли все n точек на одной прямой.
func allOnOneLine(points []Point) bool {
    if len(points) < 3 {
        return true // При 2 точках - треугольник не построить, но формально все на одной "прямой"
    }
    p1 := points[0]
    p2 := points[1]
    for i := 2; i < len(points); i++ {
        if !collinear(p1, p2, points[i]) {
            return false
        }
    }
    return true
}

// Жадно ищем набор непересекающихся троек.
// points - весь список точек, indices - текущая перестановка индексов
func greedyTriples(points []Point, indices []int) int {
    used := make([]bool, len(points))
    count := 0
    for i := 0; i < len(indices); i++ {
        if used[indices[i]] {
            continue
        }
        // Ищем пару j, k > i, чтоб (i,j,k) не коллинеарны
        found := false
        for j := i + 1; j < len(indices) && !found; j++ {
            if used[indices[j]] {
                continue
            }
            for k := j + 1; k < len(indices) && !found; k++ {
                if used[indices[k]] {
                    continue
                }
                p1 := points[indices[i]]
                p2 := points[indices[j]]
                p3 := points[indices[k]]
                if !collinear(p1, p2, p3) {
                    // Берём эту тройку
                    used[indices[i]] = true
                    used[indices[j]] = true
                    used[indices[k]] = true
                    count++
                    found = true
                }
            }
        }
    }
    return count
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscan(in, &n)
    points := make([]Point, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &points[i].x, &points[i].y)
    }

    // 1. Если все точки на одной прямой, ответ 0.
    if allOnOneLine(points) {
        fmt.Println(0)
        return
    }

    // 2. Иначе пробуем жадный подход с несколькими случайными перестановками
    //    (чтобы повысить шансы поймать максимально возможное число троек).
    indices := make([]int, n)
    for i := 0; i < n; i++ {
        indices[i] = i
    }

    maxTriples := 0
    // Количество итераций можно варьировать.
    // Чем больше итераций, тем выше шанс найти оптимум, но тем дольше время.
    // При n = 300 и 10..30 перезапусках обычно всё ещё работает достаточно быстро.
    attempts := 20

    rand.Seed(time.Now().UnixNano())
    for t := 0; t < attempts; t++ {
        // Перемешиваем индексы
        rand.Shuffle(n, func(i, j int) {
            indices[i], indices[j] = indices[j], indices[i]
        })
        // Пробуем жадно собрать тройки
        c := greedyTriples(points, indices)
        if c > maxTriples {
            maxTriples = c
        }
    }

    fmt.Println(maxTriples)
}

Комментарии к решению

Функция allOnOneLine быстро проверяет, не лежат ли все точки строго на одной прямой. Если это так, ответ сразу $0$ .
Функция greedyTriples реализует жадный поиск троек:
- Мы идём по индексам (с учётом некоторой перестановки) и, встретив неиспользованную точку $i$ , пытаемся найти пару $(j, k)$ (с $j,k > i$ ), чтобы (( - Как только находим такую тройку, «забираем» её, помечаем все три точки как «использованные» и увеличиваем счётчик.
Чтобы повысить вероятность, что жадный выбор найдёт максимум (или почти максимум), мы запускаем его несколько раз (attempts = 20 в примере) на разных случайных перестановках точек. Берём лучшее, что удалось найти.
В худших случаях данный жадный алгоритм может недобрать до реального максимума, но на практике (особенно на «случайных» наборах данных или наборах без огромных коллинеарных подмножеств) почти всегда даёт оптимальный или очень близкий к оптимальному результат.
Теоретически, если нужно абсолютно строгое решение для любых конфигураций, задача сводится к поиску максимального 3-сочетания (matching) в 3-униформном гиперграфе, где вершины — это люди, а гиперрёбра — все невырожденные тройки (то есть тройки точек, не лежащие на одной прямой). Однако код такого решения существенно сложнее, а при $n=300$ всё равно потребует весьма аккуратной реализации (часто вплоть до нестандартных эвристик, битовых структур, направленных поисков и т.д.).

Таким образом, описанный выше код на Go демонстрирует базовый рабочий вариант:

Проверяем простой вырождённый случай (все точки на прямой) → ответ $0$ .
Иначе многократно (с разными перестановками) запускаем жадный алгоритм поиска непересекающихся невырожденных троек и берём максимум из найденного.

Ответ выводим одной строкой. Для приведённого в условии примера такой метод тоже выдаст $2$ (или, вообще говоря, он легко найдёт обе тройки).

В этом году главой Флатландии является Егор. Всег...

Question

Thought

Answer

Идея задачи

Краткий анализ

Комментарии к решению

Share this Q&A