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