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

go
package main

import (
    "bufio"
    "fmt"
    "io"
    "math"
    "os"
    "strconv"
)

// Функция быстрого ввода.
func readInts(r *bufio.Reader) []int64 {
    line, err := r.ReadString('\n')
    if err != nil && err != io.EOF {
        panic(err)
    }
    fields := make([]int64, 0, 2)
    start := 0
    for i := 0; i < len(line); i++ {
        if line[i] == ' ' || line[i] == '\n' {
            if start < i {
                num, _ := strconv.ParseInt(line[start:i], 10, 64)
                fields = append(fields, num)
            }
            start = i + 1
        }
    }
    return fields
}

// Нахождение НОД (наибольшего общего делителя) неотрицательных чисел.
func gcd(a, b int64) int64 {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

// Модуль (для int64).
func abs(x int64) int64 {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    // Читаем вход.
    reader := bufio.NewReader(os.Stdin)
    line, _ := reader.ReadString('\n')
    n64, _ := strconv.ParseInt(line, 10, 64)
    n := int(n64)
    points := make([][2]int64, n)
    for i := 0; i < n; i++ {
        coords := readInts(reader)
        points[i][0] = coords[0]
        points[i][1] = coords[1]
    }

    // Если вдруг (хотя по условию n>=3).
    if n < 3 {
        fmt.Println(0)
        return
    }

    // Ищем наибольшее кол-во коллинеарных точек (k).
    // Алгоритм: для каждой точки считаем, сколько других лежит
    // на одной прямой со slope=(dx,dy). O(n^2).
    maxCollinear := 1
    for i := 0; i < n; i++ {
        slopeCount := make(map[[2]int64]int)
        // Считаем направления от points[i] к остальным.
        for j := i + 1; j < n; j++ {
            dx := points[j][0] - points[i][0]
            dy := points[j][1] - points[i][1]

            // Нормализуем (dx, dy) чтобы учесть знак и сократить дробь.
            if dx < 0 {
                dx = -dx
                dy = -dy
            } else if dx == 0 && dy < 0 {
                // Вертикаль — сохраним как (0, 1), но с учётом знака dy.
                dy = -dy
            }

            g := gcd(abs(dx), abs(dy))
            if g != 0 {
                dx /= g
                dy /= g
            }
            slopeCount[[2]int64{dx, dy}]++
        }
        // наибольшее число точек, лежащих на прямой с точкой i, это localMax + 1
        localMax := 0
        for _, c := range slopeCount {
            if c > localMax {
                localMax = c
            }
        }
        if localMax+1 > maxCollinear {
            maxCollinear = localMax + 1
        }
    }

    // Применяем формулу из анализа:
    // k = maxCollinear.
    // 1) Если все n точек коллинеарны, ответ 0
    // 2) Если k = n-1, ответ 1
    // 3) Если k = n-2, ответ зависит от n:
    //       - если n >= 6, то 2
    //       - иначе 1
    // 4) Иначе ответ floor(n/3)

    if maxCollinear == n {
        // Все точки коллинеарны
        fmt.Println(0)
        return
    }
    if maxCollinear == n-1 {
        // n-1 точка на одной прямой, одна снаружи
        fmt.Println(1)
        return
    }
    if maxCollinear == n-2 {
        if n >= 6 {
            fmt.Println(2)
        } else {
            // для n=4 или n=5 формируется не более 1 треугольника
            fmt.Println(1)
        }
        return
    }

    // Во всех остальных случаях:
    fmt.Println(n / 3)
}

Пояснения к решению:

1. Считаем количество точек n.
2. Считываем координаты всех n точек.
3. Находим k — максимальное число точек, лежащих на одной прямой. Это делается путём перебора каждой точки i и построением слопов (dx, dy) до остальных. Внутри пары (dx, dy) сокращаем дробь и нормализуем знак, чтобы разные точки на одной прямой считались одинаковым ключом. Для каждой точки считаем в словаре, сколько раз встречается одно и то же направление. Максимум по этому словарю + 1 (сама точка i) даёт нам, сколько точек лежит на одной прямой вместе с i. Глобальный максимум по всем i и есть k.
4. По найденному k применяем формулу:
   • Если k = n, значит все точки коллинеарны, ответ 0.
   • Если k = n-1, значит все, кроме одной точки, коллинеарны, и можно составить только один невырожденный треугольник (2 коллинеарные + 1 вне линии).
   • Если k = n-2, то если n ≥ 6, можно составить 2 треугольника (каждый: 2 коллинеарные из этой большой линии + 1 вне линии), иначе только 1.
   • Во всех остальных случаях ответ равен floor(n/3).

Так как n ≤ 300, описанное решение по времени работает достаточно быстро (O(n^2) на поиск максимального числа коллинеарных точек).