Транспортный справочник
15.06.2024, 18:13. Показов 3746. Ответов 24
На вход подается файл с информацией об остановках:
Кликните здесь для просмотра всего текста
13
Stop Tolstopaltsevo: 55.611087, 37.20829
Stop Marushkino: 55.595884, 37.209755
Bus 256: Biryulyovo Zapadnoye > Biryusinka > Universam > Biryulyovo Tovarnaya > Biryulyovo Passazhirskaya > Biryulyovo Zapadnoye
Bus 750: Tolstopaltsevo - Marushkino - Rasskazovka
Stop Rasskazovka: 55.632761, 37.333324
Stop Biryulyovo Zapadnoye: 55.574371, 37.6517
Stop Biryusinka: 55.581065, 37.64839
Stop Universam: 55.587655, 37.645687
Stop Biryulyovo Tovarnaya: 55.592028, 37.653656
Stop Biryulyovo Passazhirskaya: 55.580999, 37.659164
Bus 828: Biryulyovo Zapadnoye > Universam > Rossoshanskaya ulitsa > Biryulyovo Zapadnoye
Stop Rossoshanskaya ulitsa: 55.595579, 37.605757
Stop Prazhskaya: 55.611678, 37.603831
6
Bus 256
Bus 750
Bus 751
Stop Samara
Stop Prazhskaya
Stop Biryulyovo Zapadnoye
Вывод должен быть таким:
Кликните здесь для просмотра всего текста
Bus 256: 6 stops on route, 5 unique stops, 4371.02 route length
Bus 750: 5 stops on route, 3 unique stops, 20939.5 route length
Bus 751: not found
Stop Samara: not found
Stop Prazhskaya: no buses
Stop Biryulyovo Zapadnoye: buses 256 828
Не могу понять что не так с программой, отрабатывает нормально все, кроме расчета расстояния между остановками
main.cpp
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include "stat_reader.h"
#include "input_reader.h"
#include "transport_catalogue.h"
int main()
{
transport::TransportCatalogue catalogue;
std::ifstream inputFile("tsB_case2_input.txt");
//std::ofstream outputFile("output.txt");
reader::Input(catalogue, inputFile);
reader::Output(catalogue, inputFile, std::cout);
inputFile.close();
//outputFile.close();
} |
|
geo.cpp
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #pragma once
#include <cmath>
namespace geo
{
struct Coordinates
{
double latitude = 0.0; // ширина
double longitude = 0.0; // долгота
bool operator==(const Coordinates& other) const
{
return latitude == other.latitude && longitude == other.longitude;
}
bool operator!=(const Coordinates& other) const
{
return !(*this == other);
}
};
inline double ComputeDistance(Coordinates from, Coordinates to)
{
using namespace std;
if (from == to)
{
return 0.0;
}
static const double dr = 3.1415926535 / 180.;
static const int earth_rd = 6371000;
return acos(sin(from.latitude * dr) * sin(to.latitude * dr) + cos(from.latitude * dr) * cos(to.latitude * dr) * cos(abs(from.longitude - to.longitude) * dr)) * earth_rd;
}
} // end namespace geo |
|
transport_catalogue.h
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #pragma once
#include "geo.h"
#include <string>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>
namespace transport
{
struct Stop;
struct Bus
{
std::string bus_name = ""; // название автобуса
std::vector<Stop*> stops; // вектор остановок
bool operator==(const Bus& other)
{
return bus_name == other.bus_name;
}
};
struct Stop
{
std::string stop_name = ""; // название остановки
geo::Coordinates coordinates;
std::vector<Bus*> buses; // вектор автобусов, проходящих через остановку
bool operator==(const Stop& other)
{
return stop_name == other.stop_name && coordinates == other.coordinates;
}
};
struct Distance
{
const Stop* start; // первая остановка
const Stop* finish; // следующая остановка
size_t distance = 0; // расстояние между остановками
};
class DistanceHasher
{
public:
std::size_t operator()(const std::pair<const Stop*, const Stop*> pair_stops) const noexcept
{
auto hash_1 = static_cast<const void*>(pair_stops.first);
auto hash_2 = static_cast<const void*>(pair_stops.second);
return hasher_(hash_1) * 17 + hasher_(hash_2);
}
private:
std::hash<const void*> hasher_; // хеш-функция для указателей
};
// Типы для хранения соответствия между названиями и объектами
typedef std::unordered_map<std::string_view, Stop*> StopMap;
typedef std::unordered_map<std::string_view, Bus*> BusMap;
typedef std::unordered_map<std::pair<const Stop*, const Stop*>, int, DistanceHasher> DistanceMap;
class TransportCatalogue
{
public:
void AddBus(Bus&& bus_name); // добавить автобус O(N)
void AddStop(Stop&& stop_name); // добавить маршрут O(1)
void AddDistance(std::vector<Distance> distances); // добавить расстояние O(N)
Bus* GetBus(const std::string_view bus_name); // показать автобус O(1)
Stop* GetStop(const std::string_view stop_name); // показать остановку O(1)
std::unordered_set<const Bus*> StopGetUniqBuses(const Stop* stop); // показать автобусы, проходящие через остановку O(N)
std::unordered_set<const Stop*> GetUniqStops(const Bus* bus); // показать уникальные остановки O(N)
double GetLength(Bus* bus); // показать длину маршрута O(N)
size_t GetDistanceStop(const Stop* start, const Stop* finish); // показать расстояние между двумя остановками O(1)
size_t GetDistanceToBus(Bus* bus); // показать общее расстояние для автобуса O(N)
private:
std::deque<Stop> stops; // очередь остановок
StopMap stopname_to_stop; // доступ к остановкам по названию
std::deque<Bus> buses; // очередь автобусов
BusMap busname_to_bus; // доступ к автобусам по названию
DistanceMap distance_to_stop; // расстояние между остановками
};
} // end namepsace transport |
|
transport_catalogue.cpp
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
| #include "transport_catalogue.h"
#include <execution>
namespace transport
{
void TransportCatalogue::AddBus(Bus&& bus)
{
Bus* bus_buf;
buses.push_back(std::move(bus));
bus_buf = &buses.back();
busname_to_bus.insert(BusMap::value_type(bus_buf->bus_name, bus_buf));
for (Stop* stop : bus_buf->stops)
{
stop->buses.push_back(bus_buf);
}
}
void TransportCatalogue::AddStop(Stop&& stop)
{
stops.push_back(std::move(stop));
Stop* stop_buf = &stops.back();
stopname_to_stop.insert(StopMap::value_type(stop_buf->stop_name, stop_buf));
}
void TransportCatalogue::AddDistance(std::vector<Distance> distances)
{
for (Distance distance : distances)
{
std::pair<const Stop*, const Stop*> dist_pair = std::make_pair(distance.start, distance.finish);
distance_to_stop.insert(DistanceMap::value_type(dist_pair, distance.distance));
}
}
Bus* TransportCatalogue::GetBus(const std::string_view bus_name)
{
if (busname_to_bus.empty())
{
return nullptr;
}
try
{
return busname_to_bus.at(bus_name);
}
catch (const std::out_of_range& e)
{
return nullptr;
}
}
Stop* TransportCatalogue::GetStop(const std::string_view stop_name)
{
if (stopname_to_stop.empty())
{
return nullptr;
}
try
{
return stopname_to_stop.at(stop_name);
}
catch (const std::out_of_range& e)
{
return nullptr;
}
}
std::unordered_set<const Stop*> TransportCatalogue::GetUniqStops(const Bus* bus)
{
std::unordered_set<const Stop*> unique_stops;
unique_stops.insert(bus->stops.begin(), bus->stops.end());
return unique_stops;
}
std::unordered_set<const Bus*> TransportCatalogue::StopGetUniqBuses(const Stop* stop)
{
std::unordered_set<const Bus*> unique_stops;
unique_stops.insert(stop->buses.begin(), stop->buses.end());
return unique_stops;
}
double TransportCatalogue::GetLength(Bus* bus)
{
if (!bus->stops.empty())
{
return transform_reduce(next(bus->stops.begin()), bus->stops.end(), bus->stops.begin(), 0.0, std::plus<>{},
[](const Stop* lhs, const Stop* rhs)
{
return geo::ComputeDistance(lhs->coordinates, rhs->coordinates);
});
}
}
size_t TransportCatalogue::GetDistanceStop(const Stop* start, const Stop* finish)
{
if (distance_to_stop.empty())
{
return 0;
}
auto dist_pair = std::make_pair(start, finish);
try
{
auto dist_pair = std::make_pair(start, finish);
return distance_to_stop.at(dist_pair);
}
catch (const std::out_of_range& e)
{
try
{
auto dist_pair = std::make_pair(finish, start);
return distance_to_stop.at(dist_pair);
}
catch (const std::out_of_range& e)
{
return 0;
}
}
}
size_t TransportCatalogue::GetDistanceToBus(Bus* bus)
{
size_t distance = -1;
size_t stops_size = bus->stops.size() - 1;
for (size_t i = 0; i < stops_size - 1; i++)
{
distance += GetDistanceStop(bus->stops[i], bus->stops[i + 1]);
}
return distance;
}
} // end namespace transport |
|
stat_reader.h
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #pragma once
#include "transport_catalogue.h"
#include <algorithm>
#include <fstream>
namespace reader
{
void QueryBus(transport::TransportCatalogue& catalogue, std::string_view str);
void QueryStop(transport::TransportCatalogue& catalogue, std::string_view str);
void Query(transport::TransportCatalogue& catalogue, std::string_view str);
void Output(transport::TransportCatalogue& catalogue, std::istream& input, std::ostream& output);
} // end namespace reader |
|
stat_reader.cpp
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include "stat_reader.h"
#include <iostream>
#include <iomanip>
namespace reader
{
using transport::Bus;
using transport::Stop;
void QueryBus(transport::TransportCatalogue& catalogue, std::string_view str)
{
short entry = 4;
str = str.substr(entry);
Bus* bus = catalogue.GetBus(str);
if (bus != nullptr)
{
std::cout << "Bus " << bus->bus_name << ": " << bus->stops.size() << " stops on route, " << (catalogue.GetUniqStops(bus)).size() << " unique stops, " << catalogue.GetDistanceToBus(bus) << " route length" << std::endl;
}
else
{
std::cout << "Bus " << str << ": not found" << std::endl;
}
}
void QueryStop(transport::TransportCatalogue& catalogue, std::string_view stop_name)
{
short entry = 5;
stop_name = stop_name.substr(entry);
std::unordered_set<const Bus*> unique_buses;
std::unordered_set<std::string_view> unique_buses_name;
std::vector <std::string> bus_name_v;
Stop* stop = catalogue.GetStop(stop_name);
if (stop != NULL)
{
unique_buses = catalogue.StopGetUniqBuses(stop);
if (unique_buses.size() == 0)
{
std::cout << "Stop " << stop_name << ": no buses" << std::endl;
}
else
{
std::cout << "Stop " << stop_name << ": buses ";
for (const Bus* bus : unique_buses)
{
bus_name_v.push_back(bus->bus_name);
}
std::sort(bus_name_v.begin(), bus_name_v.end());
for (std::string_view bus_name : bus_name_v)
{
std::cout << bus_name;
std::cout << " ";
}
std::cout << std::endl;
}
}
else
{
std::cout << "Stop " << stop_name << ": not found" << std::endl;
}
}
void Query(transport::TransportCatalogue& catalogue, std::string_view str)
{
if (str.substr(0, 3) == "Bus")
{
QueryBus(catalogue, str);
}
else if (str.substr(0, 4) == "Stop")
{
QueryStop(catalogue, str);
}
else
{
std::cout << "Error query" << std::endl;
}
}
void Output(transport::TransportCatalogue& catalogue, std::istream& input, std::ostream& output = std::cout)
{
std::string count = "";
std::getline(input, count);
std::string str;
std::vector<std::string> query;
int amount = stoi(count);
for (int i = 0; i < amount; ++i)
{
std::getline(input, str);
query.push_back(str);
}
for (auto& strr : query)
{
Query(catalogue, strr);
}
}
} // end namespace reader |
|
input_reader.h
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #pragma once
#include "transport_catalogue.h"
#include <iostream>
#include <fstream>
namespace reader
{
using namespace transport;
Stop SplitStop(const std::string& str);
Bus SplitBus(TransportCatalogue& catalogue, std::string_view str);
std::vector<Distance> SplitDistance(TransportCatalogue& catalogue, std::string str);
void Input(TransportCatalogue& catalogue, std::istream& input);
} // end namespace reader |
|
input_reader.cpp
Кликните здесь для просмотра всего текста
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| #include "input_reader.h"
#include "stat_reader.h"
#include <sstream>
namespace reader
{
Stop SplitStop(const std::string& str)
{
size_t twopoint_pos = str.find(':');
size_t comma_pos = str.find(',');
short entry_length = 5;
short distance = 2;
Stop stop;
stop.stop_name = str.substr(entry_length, twopoint_pos - entry_length);
stop.coordinates.latitude = stod(str.substr(twopoint_pos + distance, comma_pos - twopoint_pos - distance));
stop.coordinates.longitude = stod(str.substr(comma_pos + distance));
return stop;
}
std::vector<Distance> SplitDistance(TransportCatalogue& catalogue, std::string str)
{
std::vector<Distance> distances;
short entry_length = 5;
size_t twopoint_pos = str.find(':');
short space = 2;
std::string name = str.substr(entry_length, twopoint_pos - entry_length);
str = str.substr(str.find(',') + 1);
str = str.substr(str.find(',') + space);
while (str.find(',') != std::string::npos)
{
size_t distance = stoi(str.substr(0, str.find('m')));
std::string stop_dist_name = str.substr(str.find('m') + entry_length);
stop_dist_name = stop_dist_name.substr(0, stop_dist_name.find(','));
distances.push_back({ catalogue.GetStop(name), catalogue.GetStop(stop_dist_name), distance });
str = str.substr(str.find(',') + space);
}
std::string last_name = str.substr(str.find('m') + entry_length);
size_t distance = stoi(str.substr(0, str.find('m')));
distances.push_back({ catalogue.GetStop(name), catalogue.GetStop(last_name), distance });
return distances;
}
Bus SplitBus(TransportCatalogue& catalogue, std::string_view str)
{
short entry_length = 4;
short distance = 2;
size_t twopoint_pos = str.find(':');
Bus bus;
bus.bus_name = str.substr(entry_length, twopoint_pos - entry_length);
str = str.substr(twopoint_pos + distance);
size_t more_pos = str.find('>');
if (more_pos == std::string_view::npos)
{
size_t tire_pos = str.find('-');
while (tire_pos != std::string_view::npos)
{
bus.stops.push_back(catalogue.GetStop(str.substr(0, tire_pos - 1)));
str = str.substr(tire_pos + distance);
tire_pos = str.find('-');
}
bus.stops.push_back(catalogue.GetStop(str.substr(0, tire_pos - 1)));
size_t size_ = bus.stops.size() - 1;
for (size_t i = size_; i > 0; i--)
{
bus.stops.push_back(bus.stops[i - 1]);
}
}
else
{
while (more_pos != std::string_view::npos)
{
bus.stops.push_back(catalogue.GetStop(str.substr(0, more_pos - 1)));
str = str.substr(more_pos + distance);
more_pos = str.find('>');
}
bus.stops.push_back(catalogue.GetStop(str.substr(0, more_pos - 1)));
}
return bus;
}
void Input(TransportCatalogue& catalogue, std::istream& input)
{
std::string count;
std::getline(input, count);
if (count != "")
{
std::string str;
std::vector<std::string> buses;
std::vector<std::string> stops;
int amount = stoi(count);
short bus_distance = 3;
for (int i = 0; i < amount; ++i)
{
std::getline(input, str);
if (str != "")
{
size_t space_pos = str.find_first_not_of(' ');
str = str.substr(space_pos);
if (str.substr(0, bus_distance) != "Bus")
{
stops.push_back(str);
}
else
{
buses.push_back(str);
}
}
}
for (std::string stop : stops)
{
catalogue.AddStop(SplitStop(stop));
}
for (std::string stop : stops)
{
catalogue.AddDistance(SplitDistance(catalogue, stop));
}
for (std::string bus : buses)
{
catalogue.AddBus(SplitBus(catalogue, bus));
}
}
}
} |
|
0
|