подскажите алгоритм решения 386 задачи на acmp.ru http://www.acmp.ru/index.asp?main=task&id_task=386

Здравствуйте.

Данная задача очень проста. Странно, что для нее выставлена такая сложность, по моей субъективной оценке должно быть не больше 20%. Сходу можно придумать два варианта ее решения:

1. Дурацкий вариант. Координаты точек зададим с помощью генератора случайных чисел. И если нам повезет, то ни одна тройка точек не будет лежать на одной прямой:

#include <cstdlib>
#include <fstream>

int main() {
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    int n;
    in >> n;
    out << "YES\n";
    for (int c = 0; c < n; ++c) {
        out << rand() % 20001 - 10000 << ' ' << rand() % 20001 - 10000 << '\n';
    }
}

Если не получится, то пробуем инициализировать (srand) генератор случайных чисел каким-либо значением или текущим временем системы.

2. Нормальный вариант. Воспользуемся тем фактом, что никакие три точки, расположенные на окружности, не проходят через одну прямую и расположим требуемое число точек на окружности через равный угол. Т. к. нужно получить целочисленные координаты, то следует задать достаточно большой радиус окружности, чтобы не получить неверного результата при отбрасывании дробной части координаты.

#define _USE_MATH_DEFINES
#include <cmath>
#include <fstream>

int main() {
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    int n;
    in >> n;
    double a = 0;
    out << "YES\n";
    for (int c = 0; c < n; ++c, a += 2 * M_PI / 300) {
        out << int(cos(a) * 9999) << ' ' << int(sin(a) * 9999) << '\n';
    }
}