Zadnie Centrala telefoniczna (układ kartezjański)

Mam takie zadanie Centrala telefoniczna
To mój kod

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1000000000;

const pair<int, int> TOWER_POS = {0, 0};

#define ll long long

ll calc_distance(pair<int, int> a, pair<int, int> b){
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); //bez pierwiatkowania aby uniknac bledow
}

class House{
public:
    int profit;
    ll distance = 0;

    void load(){
        int points;
        pair<int, int> point;

        cin >> points >> profit;

        for(int i = 0; i < points; i++){
            cin >> point.first >> point.second;
            distance = max(distance, calc_distance(point, TOWER_POS));
        }
    }

    bool operator<(House & h){
        return this->distance < h.distance;
    }
};

class City{
    vector<House> houses;
    ll max_profit = 0;
    int multiplier;
public:
    void load(){
        int number_of_houses;
        cin >> number_of_houses >> multiplier;

        houses.resize(number_of_houses);

        for (int i = 0; i < number_of_houses; i++){
            houses[i].load();
        }
    }
    /*
    wersja z liczbami zmiennoprzecinkowymi
    ll calc_min_tower_hight(House & house){
        return ceil(sqrt((long double)house.distance) / multiplier);
    }
    */ 
    ll calc_min_tower_hight(House & house){
        ll left = 0;
        ll right = house.distance;

        while (left < right){
            ll mid = (left + right) / 2;
            if ((mid * multiplier) * (mid * multiplier) < house.distance)
                left = mid + 1;
            else
                right = mid;
        }

        return left;
    }

    void calc_max_profit(){
        ll profits, costs;
        profits = 0;

        sort(houses.begin(), houses.end());

        for (House house : houses){
            profits += house.profit;
            ll min_tower_hight = calc_min_tower_hight(house);
            costs = ((min_tower_hight-1) * (min_tower_hight)) / 2; // ze wzoru (n + (n+1)) / 2
            max_profit = max(max_profit, profits - costs);
        }
    }

    void show_max_profit(){
        cout << max_profit;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    City city;
    city.load();
    city.calc_max_profit();
    city.show_max_profit();
    return 0;
}

Przechodzi połowę testów, aby wykluczyć zupełnie liczby zmiennoprzecinkowe zmieniłem funkcje calc_min_tower_hight tak aby wyszukiwaniem binarnym znalazła tą minimalną wysokość wieży, niestety po zmianie jest tylko więcej błędnych wyników, co robię źle ?

Tutaj testuje

Pozycje punktów nie mieściły się w zakresie int...

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1000000000;

#define ll long long

const pair<ll, ll> TOWER_POS = {0, 0};

ll calc_distance(pair<ll, ll> a, pair<ll, ll> b){
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); //bez pierwiatkowania aby uniknac bledow
}

class House{
public:
    int profit;
    ll distance = 0;

    void load(){
        int points;
        pair<ll, ll> point;

        cin >> points >> profit;

        for(int i = 0; i < points; i++){
            cin >> point.first >> point.second;
            distance = max(distance, calc_distance(point, TOWER_POS));
        }
    }

    bool operator<(House & h){
        return this->distance < h.distance;
    }
};

class City{
    vector<House> houses;
    ll max_profit = 0;
    int multiplier;
public:
    void load(){
        int number_of_houses;
        cin >> number_of_houses >> multiplier;

        houses.resize(number_of_houses);

        for (int i = 0; i < number_of_houses; i++){
            houses[i].load();
        }
    }

    ll calc_min_tower_hight(House & house){
        return ceil(sqrt((long double)house.distance) / multiplier);
    }

    void calc_max_profit(){
        ll profits, costs;
        profits = 0;

        sort(houses.begin(), houses.end());

        for (House house : houses){
            profits += house.profit;
            ll min_tower_hight = calc_min_tower_hight(house);
            costs = ((min_tower_hight-1) * (min_tower_hight)) / 2; // ze wzoru (n + (n+1)) / 2
            max_profit = max(max_profit, profits - costs);
        }
    }

    void show_max_profit(){
        cout << max_profit;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    City city;
    city.load();
    city.calc_max_profit();
    city.show_max_profit();
    return 0;
}

przechodzi wszystkie testy

Suchy702 napisał(a):

Pozycje punktów nie mieściły się w zakresie int...

To nie jest prawda, problem miałeś w tym, że był overflow w liczeniu odległości od bazy.