• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed Zadanie centrala telefoniczna [układ kartezjański]

Object Storage Arubacloud
0 głosów
139 wizyt
pytanie zadane 10 października 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
zamknięte 10 października 2020 przez wojtek_suchy

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

komentarz zamknięcia: pozycje punktow nie miescily sie w zakresie int

Podobne pytania

0 głosów
1 odpowiedź 323 wizyt
pytanie zadane 21 kwietnia 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 457 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 180 wizyt

92,755 zapytań

141,677 odpowiedzi

320,423 komentarzy

62,101 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...