Задача на двумерные массивы.

[MooNDeaR]

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

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

[.S9]

Ну раз надо только натолкнуть на решение задачи, то воспользуйся уравнением окружности (тобиш x^2 + y^2 = R^2). Выбор точки будет таким: если все три точки принадлежат окружности (ур. обращается в тождество) то окружность, описанная вокруг треугольника существует. Ну а дальше считаешь площади и находиш необходимую разницу и пр.


Если что-то слишком подробно - то просьба не критиковать

Чуть не забыл. Разница будет минимальной если треугольник равностороний (хотя в этом точно не уверен)

[MooNDeaR]

Спасибо. Что-то совсем засох мой мозг, развивать надо. Я то искал решение в другой стороне. Искал какое-нибудь условие, при котором вокруг треугольника можно описать окружность и оттуда толкаться. Эх, вроде молодой, а мозг не соображает. Еще раз спасибо

P.S.

Решу - выложу код. Посмеёмся

[eoln]

Сообщение от .S9

...воспользуйся уравнением окружности (тобиш x^2 + y^2 = R^2). Выбор точки будет таким: если все три точки принадлежат окружности (ур. обращается в тождество) то окружность, описанная вокруг треугольника существует

Через любые три точки не принадлежащие одной прямой можно провести окружность и на построить на них треугольник. То есть координаты точек не должны быть пропорциональными.

Разница будет минимальной если треугольник равностороний (хотя в этом точно не уверен)

Правильно что не уверен. Треугольники по площади разные, если один равнобедренный большой, а другой неравнобедренный, но маленький, то уже ответ неверен.
Площадь треугольника можно найти, например, по формуле Герона. Площадь круга через радиус R=abc/4S

Точки выбирать в тройном цикле полным перебором

[MooNDeaR]

Я отказался от пляски с x^2 + y^2 = r^2
Вспомнил по поводу того, что вокруг любого треугольника можно описать окружность А тут еще и вы написали

Так что я посидел и пополнил список своих табличек в стиле "ТАК ПИСАТЬ НЕЛЬЗЯ!"

Выкладываю свой код на растерзание критикой. (P.S. написано в IDE Eclipse)

//============================================================================
// Из заданного на плоскости множества точек выбрать три различные точки так,
// чтобы разность между площадью круга, ограниченного окружностью, проходящей
// через эти три точки, и площадью треугольника с вершинами в этих точках
// была минимальной.
//============================================================================

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define NPnt 10
#define XY 2
#define PI 3.141592653589
using namespace std;

void randomfill(double(*)[XY]);
void matrix_print(double(*)[XY]);
inline double geron(double,double,double);
long factorial(int);
inline int combination(int,int);
inline double vectormod(double,double,double,double);

struct Circle
{
	double rad;
	double area;
};

struct Triangle
{
	int i;
	int j;
	int k;
	double a;
	double b;
	double c;
	double area;
};

int main() {
	double crd[NPnt][XY];
	int N = combination(NPnt,3);
	Circle MasC[N];
	Triangle MasT[N];
	int cnt = 0;
	srand(time(NULL));
	randomfill(crd);
	matrix_print(crd);
    for(int i = 0; i < (NPnt-2); i++)
    	for(int j = i+1; j < (NPnt-1); j++)
    		for(int k = j+1; k < NPnt; k++)
    		{
    			MasT[cnt].a = vectormod(crd[i][0],crd[j][0],crd[i][1],crd[j][1]);
    			MasT[cnt].b = vectormod(crd[j][0],crd[k][0],crd[j][1],crd[k][1]);
    			MasT[cnt].i = i; MasT[cnt].j = j; MasT[cnt].k = k;
    			MasT[cnt++].c = vectormod(crd[i][0],crd[k][0],crd[i][1],crd[k][1]);
    		}
    for(int i = 0; i < N; i++)
    {
    	MasT[i].area = geron(MasT[i].a,MasT[i].b,MasT[i].c);
    	MasC[i].rad = (MasT[i].a * MasT[i].b * MasT[i].c)/(4*MasT[i].area);
    	MasC[i].area = PI * MasC[i].rad * MasC[i].rad;
    }
    int buf[3] = {0,1,2};
	double min_diff = 1E18;
    for(int i = 0; i < N; i++)
    {
    	double temp = MasC[i].area - MasT[i].area;
    	if(temp < min_diff)
    	{
    		min_diff = temp;
    		buf[0] = MasT[i].i;
    		buf[1] = MasT[i].j;
    		buf[2] = MasT[i].k;
    	}
    }

    cout << "Были сделаны вычисления:" << endl;
    cout << "Минимальная разность в площадях была на точках:" << endl << endl;
    for(int i = 0; i < 3; i++)
    	cout << crd[buf[i]][0] << " " << crd[buf[i]][1] << endl << endl;
	return 0;
}

void randomfill(double mtx[][XY])
{
	for(int i = 0; i < NPnt; i++)
		for(int j = 0; j < XY; j++)
			mtx[i][j] = rand()%31 - 15;
}

void matrix_print(double mtx[][XY])
{
	cout << "Печатаю координаты:" << endl;
	cout << setw(5) << "X " << setw(4) << "Y " << endl << endl;
	for(int i = 0; i < NPnt; i++)
	{
		for(int j = 0; j < XY; j++)
			cout << setw(4) << mtx[i][j];
		cout << endl;
	}
}

inline double geron(double a,double b,double c)
{
     return 0.25*sqrt((a+b+c)*(b+c-a)*(a+c-b)*(a+b-c));
}

long factorial(int N)
{
	if(!N) return 1;
	long result = 1;
	for(int i = 1; i <= N; i++)
		result *= i;
	return result;
}

inline int combination(int n, int k)
{
	return (factorial(n)/(factorial(k)*factorial(n-k)));
}

inline double vectormod(double x1, double x2, double y1, double y2)
{
	return (sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)));
}

Прошу сильно помидорами не закидывать
Я ж только учусь.

[MooNDeaR]

Собственно у меня возник еще вопрос: а как протестировать?

[Stilet]

а как протестировать?

Тоесть? Запусти программу что она выдаст?

[MooNDeaR]

Сообщение от Stilet

Тоесть? Запусти программу что она выдаст?

Предлагаешь считать площадь и искать самому эту разницу?
Ладн, вопрос всё равно не актуален. Всё проверил, всё работает. Можно даже тему закрыть. Всем спасибо.

[Stilet]

Предлагаешь считать площадь и искать самому эту разницу?

Ну да. Первый раз вручную посчитай. Я лично для проверки брал решебники, зная их входные параметры и ответы заранее мне и просчитывать не нужно было