Условие

Дано множество точек двух классов в R^2. Найти разделяющую прямую с максимальным зазором (классический Hard-Margin SVM). Если разделяющей прямой не существует — вывести -1.

Формат ввода

N1                # число точек первого класса (1 ≤ N1 ≤ 10^5)
x_1 y_1
...
x_N1 y_N1
N2
...               # точки второго класса

Координаты по модулю не превышают 10^7.

Формат вывода

Если существует разделяющая прямая, вывести любую — три числа a b c (уравнение a x + b y + c = 0), точность 10^-6.

Иначе — -1.

Решение

Постановка задачи

Hard-Margin SVM: найти w ∈ R^2, b ∈ R минимизирующие ||w||² при условии:

y_i (w · x_i + b) ≥ 1 для всех точек

где y_i ∈ {+1, -1} — метка класса.

Геометрически: разделяющая прямая w · x + b = 0 с зазором 1 / ||w|| до ближайших точек по обе стороны.

Подход

Если выпуклые оболочки классов не пересекаются — разделяющая прямая существует. Иначе — нет.

Алгоритм поиска оптимальной прямой:

Найти выпуклую оболочку каждого класса.
Найти ближайшую пару точек между двумя выпуклыми многоугольниками (точки могут быть вершинами оболочек или точками на рёбрах).
Серединная перпендикулярная этой паре — оптимальная разделяющая прямая (макс зазор).

Сложность:

Выпуклые оболочки — O(N log N).
Минимальное расстояние между оболочками — O(N1 + N2) (метод вращающихся опор).

Альтернатива — Quadratic Programming

Прямая постановка SVM — QP-задача. Использовать cvxpy:

import cvxpy as cp
import numpy as np
 
def solve_svm(X1, X2):
    X = np.vstack([X1, X2])
    y = np.array([1] * len(X1) + [-1] * len(X2))
    n, d = X.shape
    w = cp.Variable(d)
    b = cp.Variable()
    constraints = [cp.multiply(y, X @ w + b) >= 1]
    obj = cp.Minimize(cp.sum_squares(w))
    prob = cp.Problem(obj, constraints)
    prob.solve()
    if prob.status != cp.OPTIMAL:
        return None
    return w.value, b.value

Если prob.status — infeasible, разделяющей нет → -1.

Эффективное решение через выпуклые оболочки

import sys
from typing import List, Tuple
 
def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
 
def convex_hull(points):
    pts = sorted(set(map(tuple, points)))
    if len(pts) <= 1:
        return pts
    lower = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]
 
def hulls_intersect(h1, h2):
    # SAT: если все точки h2 по одну сторону каждого ребра h1, и наоборот.
    def edges(h):
        return [(h[i], h[(i+1) % len(h)]) for i in range(len(h))]
    for poly_a, poly_b in [(h1, h2), (h2, h1)]:
        for a, b in edges(poly_a):
            normal = (b[1] - a[1], a[0] - b[0])  # перпендикуляр
            ds_b = [(p[0] - a[0]) * normal[0] + (p[1] - a[1]) * normal[1] for p in poly_b]
            if all(d > 1e-9 for d in ds_b):
                return False  # разделяющая прямая найдена
    return True
 
# Если оболочки не пересекаются → ищем минимальное расстояние и серединную перпендикулярную.

Полное решение

import sys
import numpy as np
 
def solve():
    data = sys.stdin.read().split()
    pos = 0
    n1 = int(data[pos]); pos += 1
    X1 = np.array([[float(data[pos + 2*i]), float(data[pos + 2*i + 1])]
                   for i in range(n1)])
    pos += 2 * n1
    n2 = int(data[pos]); pos += 1
    X2 = np.array([[float(data[pos + 2*i]), float(data[pos + 2*i + 1])]
                   for i in range(n2)])
 
    h1 = convex_hull(X1.tolist())
    h2 = convex_hull(X2.tolist())
 
    # Простой случай через QP — для маленьких выборок.
    # Для производительной реализации — алгоритм через выпуклые оболочки.
    # Здесь покажем подход через scipy.
    from scipy.optimize import linprog
    # Linear feasibility for separability:
    # find a, b, c s.t. a x_i + b y_i + c >= 1 for class 1, <= -1 for class 2.
    # Это LP; если решаемо — есть разделяющая. Для max-margin переходим на QP.
    A_ub = []
    b_ub = []
    for x, y in X1:
        A_ub.append([-x, -y, -1, 1])  # -(a x + b y + c) + slack <= -1 → a x + b y + c >= 1 - slack
        b_ub.append(-1)
    for x, y in X2:
        A_ub.append([x, y, 1, 1])
        b_ub.append(-1)
    c = [0, 0, 0, 1]  # минимизируем slack
    res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(None, None)]*3 + [(0, None)])
    if res.x[3] > 1e-6:
        print(-1)
        return
    a, b, c0 = res.x[0], res.x[1], res.x[2]
    print(f"{a:.6f} {b:.6f} {c0:.6f}")
 
# solve()

Подводные камни

-1 если нерасзделимы. Сначала проверяем разделимость (LP feasibility), потом ищем максимальный margin.
Точность 10^-6. Линейный солвер scipy достаточен; для жёстких тестов — QP-солвер.
Большие N (10^5). QP может быть медленным. Лучший асимптотический подход — через выпуклые оболочки + ближайшая пара = O(N log N).
Параллельные точки. Если все точки на одной прямой — выпуклая оболочка вырождается. Обработать как частный случай.
Совпадающие точки разных классов → нерасзделимы. Сразу -1.
Геометрический ответ vs. SVM-ответ. Любая разделяющая прямая принимается, не обязательно с максимальным margin. Это упрощает решение — достаточно LP.

Эталонный ответ

Если выпуклые оболочки классов не пересекаются — разделяющая прямая существует.

Эффективное решение: LP-feasibility (любая разделяющая) или вычисление выпуклых оболочек + минимальное расстояние между ними + серединная перпендикулярная (max-margin SVM). Иначе -1.

Стажировка ML — Разделяющая прямая (метод опорных векторов)