# Untitled

unknown

python

a year ago

2.1 kB

3

Indexable

Never

^{}

import math class Town: def __init__(self, x, y, population): self.x = x self.y = y self.population = population def distance_to(self, other_town): return math.sqrt((self.x - other_town.x) ** 2 + (self.y - other_town.y) ** 2) class WirelessTower: def __init__(self, x, y): self.x = x self.y = y self.covered_population = 0 def calculate_coverage(self, towns): for town in towns: if town.distance_to(self) <= d: self.covered_population += town.population class CoverageCalculator: @staticmethod def calculate_covered_population(towns, towers): for tower in towers: tower.calculate_coverage(towns) def main_algorithm(n, p, d, town_data): towns = [] for x, y, population in town_data: towns.append(Town(x, y, population)) initial_tower = WirelessTower(0, 0) # Place the initial tower arbitrarily towers = [initial_tower] for _ in range(p - 1): max_population_covered = 0 best_town = None for town in towns: if town not in [tower for tower in towers]: temp_towers = towers + [WirelessTower(town.x, town.y)] CoverageCalculator.calculate_covered_population(towns, temp_towers) total_covered_population = sum(tower.covered_population for tower in temp_towers) if total_covered_population > max_population_covered: max_population_covered = total_covered_population best_town = town if best_town: towers.append(WirelessTower(best_town.x, best_town.y)) return towers # Input parsing n, p, d = map(int, input().split()) town_data = [list(map(int, input().split())) for _ in range(n)] towers = main_algorithm(n, p, d, town_data) for tower in towers: print(town_data.index((tower.x, tower.y, 0)) + 1, end=' ') total_covered_population = sum(tower.covered_population for tower in towers) print(total_covered_population)