Геометрическая задачка

[genroelgvozo]

Итак одна геометричесая задача. Прошу сказать кто какое решение видит.
Даны N точек в трехмерном пространстве (координаты известны)
найти координаты точки, такой что, расстояние от нее до самой дальней из данных точек было бы наименьшим из всех возможных

[dsd]

Центр что ли?
1.Берешь для каждой точки и в цикле узнаешь максимальное расстояние до точки из множества. Пишешь данные в массив array[n]. Потом выбираешь из массива ту у которой минимальное значение. Это будет та точка.

2.Еще можно для каждой посчитать сумму всех расстояний до других точек и выбрать ту, что с минимальной суммой.
В первом варианте получится точка где-то по центру множества, а во втором там где плотность выше.

[den]

Мой вариант:
1) сложить все x|y|z точек и поделить на N. Получим cx, cy, cz
2) Перебрать все точки, находить растояние от неё до С. r = (cx-x)^2+(cy-y)^2+(cz-z)^2
(корень убрать для скорости)
3) та, у которой r минимальна - исходная



upd: вот накатал =)

#include <cstdio>

struct point
{
    float x, y, z;
    point()
    {
        x = 0;
        y = 0;
        z = 0;
    }
};

float get_r(point a, point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}

int main()
{
    int n;
    scanf("%d", &n);
    point c;
    point *mas = new point[n];

    for(int i = 0; i < n; i++)
    {
        scanf("%f %f %f", &mas[i].x, &mas[i].y, &mas[i].z);
        c.x += mas[i].x;
        c.y += mas[i].y;
        c.z += mas[i].z;
    }

    c.x /= n;
    c.y /= n;
    c.z /= n;

    float min_r = get_r(mas[0], c);
    int min_i = 0;

    for(int i = 1; i < n; i++)
    {
        float r = get_r(mas[1], c);
        if(r < min_r)
        {
            min_r = r;
            min_i = i;
        }
    }

    printf("\n%f %f %f\n", mas[min_i].x, mas[min_i].y, mas[min_i].z);

    return 0;
} 


[genroelgvozo]

Мда, извеняюсь не правильно написал
найти другую точку (отличную от данных) такую чтобы, от неет растояние до самой дальней из данных точек было наименьшим

Кстати Ден, ты случаем на кодфорсес не обитаешь?)
а то твою темку увидел про проверяющую систему, и задачка про префиксы вроде как оттуда, хотя может и с тимуса

[den]

Мда, извеняюсь не правильно написал
найти другую точку (отличную от данных) такую чтобы, от неет растояние до самой дальней из данных точек было наименьшим

ну тогда:
сложить все x|y|z точек и поделить на N. Получим cx, cy, cz - координаты искомой точки.

#include <cstdio>

int main()
{
    int n;
    float cx = 0, cy = 0, cz = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) 
    {
        float x, y, z;
        scanf("%f %f %f", &x, &y, &z);
        cx += x;
        cy += y;
        cz += z;
    }
    printf("\n%f %f %f\n", cx/n, cy/n, cz/n);
} 


хотя что уж слишком просто, наверника неправильно

Кстати Ден, ты случаем на кодфорсес не обитаешь?)
а то твою темку увидел про проверяющую систему, и задачка про префиксы вроде как оттуда, хотя может и с тимуса

на кодефорсес иногда решаю
а ещё на нашем сайте: contester.tsure.ru

[dsd]

Ужасный инженерный способ:
Представляешь, что у каждой точки есть масса. Считаешь общий момент инерции относительно произвольной точки.

Твоя точка это та в которой момент инерции минимальный. Есть маааленькая кучка формул из термеха как находить весь этот ужас и считать момент инерции относительно другой оси если известен относительно другой. Из них можно выкопать нужный алгоритм. И это будет правильно, но надо ли оно тебе?

Центр тяжести.
Центром тяжести тела называется точка, относительно которой суммарный момент сил тяжести, действующих на систему, равен нулю. Например, в системе, состоящей из двух одинаковых масс, соединённых несгибаемым стержнем, и помещённой в неоднородное гравитационное поле (например, планеты), центр масс будет находиться в середине стержня, в то время как центр тяжести системы будет смещён к тому концу стержня, который находится ближе к планете (ибо вес массы P = m·g зависит от параметра гравитационного поля g), и, вообще говоря, даже расположен вне стержня.

Можно для двух-трех точек определить вектор направления гравитации. Поидее они пересекутся, там центр тяжести

В твоем случае f=G*m*M/R^2

Здесь G — гравитационная постоянная, равная примерно 6,6725Ч10-11 мі/(кг·сІ).

Направлена по вектору соединяющему точку для которой считаешь. Складываешь N векторов. результат показывает в сторону центра тяжести.

[genroelgvozo]

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

[genroelgvozo]

Да именно, тут не сумарный момент минимален (ну или равен нулю) а лишь одно расстояние
вот пример
5 точек
5 0 0
-5 0 0
0 3 4
4 -3 0
2 2 -2
центр тяжести для них (при условии равенства масс) 1.2 0.4 0.4
а ответ к задаче точка 0 0 0
от этой точки расстояние до самой дальней наименьшее

[dsd]

Момент инерции зависит от расстояний масс от оси инерции, где минимальный там расстояния наименьшие.

[genroelgvozo]

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

[genroelgvozo]

Все таки я нашел точное решение, которое работает за O(n^4) что достаточно много
Короче по теореме хелли и следующей из нее теореме юнга можно перебрать все двойки тройки и четверки точек и найти центр наименьшего шара, включающих их. После выбрать центр наименьшего из полученных шаров. Но такое решение в систему по времени не проходит, проходит только приближенное
там по условие может быть погрешность не больше 10-6
ну а численных решений неколько, самое быстрое это три вложенных тернарных поиска по координатам (хотя многие делали и одним)

[alcoSHoLiK]

Интересная задачка. Только по-моему, это задача оптимизации, поэтому физическими способами ее и не получается решить. Для практических задач эффективней искать численным способом решение, мне кажется. Есть разные итеративные методы.

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

[genroelgvozo]

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