Top.Mail.Ru
Ответы
Аватар пользователя
maga_maga_4266
1г
Изменено
Аватар пользователяПрограммирование

Тернарный поиск с++

Изображение

Задача с codeforces. Я так понял тут надо использовать тернарный поиск

#include <bits/stdc++.h>

using namespace std;

struct Point {
int x, y;
};


const int max_coord = 10000;
const double eps = 0.01;



double dist(Point p1, Point p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

double total_dist(Point target, vector<Point>& points) {
double sum = 0;
for (const Point& p : points) {
sum += dist(target, p);
}
return sum;
}

Point ternary_search(vector<Point>& points) {
double left = -max_coord, right = max_coord;

while (right - left > eps) {
double m1 = left + (right - left) / 3;
double m2 = right - (right - left) / 3;

Point p1 = {m1, m1};
Point p2 = {m2, m2};

double d1 = total_dist(p1, points);
double d2 = total_dist(p2, points);

if (d1 < d2) {
right = m2;
} else {
left = m1;
}
}

return {left, left};
}

int main() {
int n;
cin >> n;

vector<Point> points;
points.resize(n);

for (int i = 0; i < n; ++i) {
cin >> points[i].x >> points[i].y;
}

Point result = ternary_search(points);

cout << result.x << " " << result.y << endl;

return 0;
}

Вот код который я написал. выдает ошибку на 4 тесте. Если вводить значения из примера, то все работает. А когда пытаюсь загрузить на кодфорс - ошибка. Помогите пожалуйста.

По дате
По рейтингу
Аватар пользователя
user49913
Новичок
1г

я бы для начала eps поменьше поставил - прям сильно поменьше, этак 1e-6 или даже меньше, дабл всё стерпит
перфу от этого хуже не станет, а точек у тебя всё-таки 50: если ты на 0.1 ошибся в координате, ошибку по сумме расстояний можно как раз на N домножать

дальше: а ты почему точку на прямой x=y ищешь? тебе надо искать по всей плоскости, для этого нужно два вложенных тернарных поиска делать, внешний, например, перебирает x и минимизирует min(total_dist(x, y)) по всем y при заданном x, а внутренний как раз ищет этот самый min, подбирая лучший игрек

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

ну и да, тесты надо делать самому... тут всё-таки макс ошибка 0.1, можно было бы и сделать генератор рандомных тестов с небольшими по модулю координатами и самому понаходить баги

Аватар пользователя
z9xsvoipgjphzyl
Искусственный Интеллект
1г

А если так...

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
 #include <iostream> 
#include <vector> 
#include <cmath> 
 
struct Point { 
    int x, y; 
}; 
 
const double eps = 0.01; 
 
double dist(const Point& p1, const Point& p2) { 
    return hypot(p1.x - p2.x, p1.y - p2.y); 
} 
 
double total_dist(const Point& target, const std::vector<Point>& points) { 
    double sum = 0; 
    for (const Point& p : points) { 
        sum += dist(target, p); 
    } 
    return sum; 
} 
 
Point ternary_search(const std::vector<Point>& points) { 
    double left = -10000, right = 10000; 
 
    while (right - left > eps) { 
        double m1 = left + (right - left) / 3; 
        double m2 = right - (right - left) / 3; 
 
        Point p1 = {static_cast<int>(m1), static_cast<int>(m1)}; 
        Point p2 = {static_cast<int>(m2), static_cast<int>(m2)}; 
 
        double d1 = total_dist(p1, points); 
        double d2 = total_dist(p2, points); 
 
        if (d1 < d2) { 
            right = m2; 
        } else { 
            left = m1; 
        } 
    } 
 
    return {static_cast<int>(left), static_cast<int>(left)}; 
} 
 
int main() { 
    int n; 
    std::cin >> n; 
 
    std::vector<Point> points(n); 
 
    for (int i = 0; i < n; ++i) { 
        std::cin >> points[i].x >> points[i].y; 
    } 
 
    Point result = ternary_search(points); 
 
    std::cout << result.x << " " << result.y << std::endl; 
 
    return 0; 
}
Больше по теме