Editorial for Teleport

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

import math

RADIUS = 6371

def calc_distance(lat1, lng1, lat2, lng2):
    lat1 = math.radians(lat1)
    lat2 = math.radians(lat2)
    lng1 = math.radians(lng1)
    lng2 = math.radians(lng2)

    x = (lng2 - lng1) * math.cos((lat1 + lat2) / 2)
    y = lat2 - lat1
    return RADIUS * ((x**2 + y**2)**0.5)

def solve(N, lat, lng, cities):
    curr_money = 0
    money_at_leave = [[0, (lat, lng), -1]]
    current = (lat, lng)

    # calculate money at leave
    for i, city in enumerate(cities):
        fee = calc_distance(current[0], current[1], city[0], city[1])
        earn = city[2]

        current = (city[0], city[1])
        curr_money += earn - fee

        money_at_leave.append([curr_money, current, i])

    # calculate return
    for values in money_at_leave:
        fee = calc_distance(lat, lng, values[1][0], values[1][1])
        values[0] -= fee

    money_at_leave.sort(reverse=True)

    return max(money_at_leave)[2] + 1

if __name__ == '__main__':
    N, lat, lng = map(float, input().strip().split())
    N = int(N)

    cities = []
    for _ in range(N):
        values = list(map(float, input().strip().split()))
        cities.append(values)

    print(solve(N, lat, lng, cities))