#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>

typedef struct point {
	double x;
	double y;
	int flag;
}POINT;

double func(double x) {
	return pow((x - 2), 2);
}

double calcDot(double (*func)(double), double L, double x1, double x2) {
	return 1 / (2 * L) * (L * (x1 + x2) + func(x1) - func(x2));
}

double lowGrade(double (*func)(double), double L, double x1, double x2) {
	return (func(x1) + func(x2)) / 2 - L / 2 * (x2 - x1);
}

double calcL(double a, double b) {
	if ((2 * (a - 2)) > (2 * (b - 2))) {
		return (2 * (a - 2));
	}
	else {
		return (2 * (b - 2));
	}
}



int main() {
	POINT arr[1000] = { 0 };

	double a = 0, b = 5, accuracy = 0.1, L = calcL(a, b);
	double y = calcDot(&func, L, a, b);
	arr[0] = { a, func(a), 0 };
	arr[1] = { y,func(y),1 };
	arr[2] = { b,func(b),0 };
	int f = 2;
	double upperLimit = fmin(arr[0].y, arr[2].y);
	double lowerLimit = lowGrade(&func, L, a, b);

	int n = 1;

	while (upperLimit - lowerLimit > accuracy) {
		double min = upperLimit;
		int r = 0;
		for (int i = 0; i < f + 1; i++) {
			if ((arr[i].flag != 0) && (lowerLimit <= arr[i].y) && (arr[i].y < min)) {
				min = arr[i].y;
				r = i;
			}
		}
		upperLimit = fmin(upperLimit, func(arr[r].x));
		lowerLimit = min;

		arr[r].y = func(arr[r].x);
		arr[r].flag = 0;
		arr[f + 2] = { arr[f].x,arr[f].y,arr[f].flag };
		arr[r + 1] = { arr[r].x,arr[r].y,arr[r].flag };
		arr[r] = { calcDot(&func,L,arr[r-1].x,arr[r].x), lowGrade(&func, L, arr[r-1].x,arr[r].x), 1 };
		arr[r + 2] = { calcDot(&func,L,arr[r].x,arr[r + 1].x), lowGrade(&func, L, arr[r].x,arr[r + 1].x), 1 };
		n++;
	}
	printf("[%.4lf;%.4lf]\nIteretion:%d", lowerLimit, upperLimit, n);

	return 0;
}