#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <stdio.h>

// Расстояние от точки до окружности
double distance(double r, double center_x, double center_y, double x, double y) {
    return sqrt(pow(x - center_x, 2) + pow(y - center_y, 2)) - r;
}

// Сумма квадратов расстояний
double sum(double points[2][36], double r, double center_x, double center_y) {
    double sum = 0;

    for (int i = 0; i < 36; i++) {
        sum += pow(distance(r, center_x, center_y, points[0][i], points[1][i]), 2);
    }

    return sum;
}

int main()
{
    setlocale(LC_ALL, "RUS");

    FILE *file = nullptr;

    fopen_s(&file, "file.txt", "r"); // <- Считываем файл

    if (!file) {
        printf("Не удалось открыть файл\n");
        return -1;
    }

    char buff[100]; // <- Буфер

    double points[2][36]; // <- Входные данные

    double x, y;

    int i = 0;

    // 1. Считываем входные данные

    while (fgets(buff, 100, file)) {
        if (std::string(buff).empty()) break;

        sscanf_s(buff, "%lf %lf", &x, &y);

        points[0][i] = x;
        points[1][i] = y;

        i++;
    }

    fclose(file);

    // 2. Начальное приближение

    double minX = points[0][0]
         , maxX = points[0][0]
         , minY = points[1][0]
         , maxY = points[1][0];

    // Поиск минимальной и максимальной координаты по Оси X и Y

    for (i = 0; i < 36; i++) {
        minX = std::min(minX, points[0][i]);
        maxX = std::max(maxX, points[0][i]);
        minY = std::min(minY, points[1][i]);
        maxY = std::max(maxY, points[1][i]);
    }

    double centerX = (minX + maxX) / 2.0 // <- Центр окружности (x, y)
         , centerY = (minY + maxY) / 2.0;

    double radius = ((abs(maxX - minX) / 2.0) + (abs(maxY - minY) / 2.0)) / 2.0; // <- Радиус окружности

    // 3. Метод Дихтемии

    double eps = 1e-2; // <- Точность

    printf("Введите погрешность (eps): \n");
    std::cin >> eps;

    double oldCenterX = centerX, newCenterX = oldCenterX
        , oldCenterY = centerY, newCenterY = oldCenterY
        , oldRadius = radius, newRadius = oldRadius;

    double a, b, c;

    int j = 0; // <- Количество итераций

    do {
        // Обновляем данные

        oldRadius = newRadius;
        oldCenterX = newCenterX;
        oldCenterY = newCenterY;

        // Смещаем окружность по оси X

        a = minX;
        b = maxX;

        while (abs(b - a) > eps) {
            c = (b + a) / 2.0;

            if (sum(points, oldRadius, c - eps, oldCenterY) > sum(points, oldRadius, c + eps, oldCenterY))
                a = c;
            else
                b = c;
        }

        newCenterX = c;

        // Смещаем окружность по оси Y

        a = minY;
        b = maxY;

        while (abs(b - a) > eps) {
            c = (b + a) / 2.0;

            if (sum(points, oldRadius, oldCenterX, c - eps) > sum(points, oldRadius, oldCenterX, c + eps))
                a = c;
            else
                b = c;
        }

        newCenterY = c;

        // Подгоняем радиус окружности

        a = std::min(abs(maxX - minX) / 2.0, abs(maxY - minY) / 2.0);
        b = std::max(abs(maxX - minX) / 2.0, abs(maxY - minY) / 2.0);

        while (abs(b - a) > eps) {
            c = (b + a) / 2.0;

            if (sum(points, c - eps, oldCenterX, oldCenterY) > sum(points, c + eps, oldCenterX, oldCenterY))
                a = c;
            else
                b = c;
        }

        newRadius = c;

        j++;

    } while (abs(newCenterX - oldCenterX) > eps && abs(newCenterY - oldCenterY) > eps && abs(newRadius - oldRadius) > eps);

    // 4. Выводим результат программы

    printf("\nНачальное приближение: Окружность с центром (%lf, %lf) и радиусом %lf", centerX, centerY, radius);
    printf("\nРезультат: Окружность с центром (%lf, %lf) и радиусом %lf", newCenterX, newCenterY, newRadius);
    printf("\nПотребовалось итераций: %i\n\n", j);

    system("pause");

    return 0;
}