Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
- #include <bits/stdc++.h>
- #include <optional>
- using namespace std;
- const long double PI = 3.1415926535;
- pair<string_view, optional<string_view>> SplitTwoStrict(string_view s, string_view delimiter = " ") {
- const size_t pos = s.find(delimiter);
- if (pos == s.npos) {
- return { s, nullopt };
- }
- else {
- return { s.substr(0, pos), s.substr(pos + delimiter.length()) };
- }
- }
- vector<string_view> split(string_view s, string_view delimer = " ") {
- size_t pos = s.find(delimer);
- vector<string_view> ans;
- if (pos == s.npos && s.length()) {
- ans.push_back(s);
- }
- else
- while (pos != s.npos) {
- pos = s.find(delimer);
- ans.push_back(s.substr(0, pos));
- s = s.substr(pos + delimer.length());
- }
- return ans;
- }
- pair<string_view, string_view> SplitTwo(string_view s, string_view delimiter = " ") {
- const auto [lhs, rhs_opt] = SplitTwoStrict(s, delimiter);
- return { lhs, rhs_opt.value_or("") };
- }
- string_view ReadToken(string_view& s, string_view delimiter = " ") {
- const auto [lhs, rhs] = SplitTwo(s, delimiter);
- s = rhs;
- return lhs;
- }
- int ConvertToInt(string_view str) {
- // use std::from_chars when available to git rid of string copy
- size_t pos;
- const int result = stoi(string(str), &pos);
- if (pos != str.length()) {
- std::stringstream error;
- error << "string " << str << " contains " << (str.length() - pos) << " trailing chars";
- throw invalid_argument(error.str());
- }
- return result;
- }
- double ConvertToDouble(string_view str) {
- // use std::from_chars when available to git rid of string copy
- size_t pos;
- const double result = stod(string(str), &pos);
- if (pos != str.length()) {
- std::stringstream error;
- error << "string " << str << " contains " << (str.length() - pos) << " trailing chars";
- throw invalid_argument(error.str());
- }
- return result;
- }
- string compressSpaces(string s) {
- string ans;
- for (auto ch : s) {
- if (ans.size() && ans.back() == ' ' && ch == ' ') continue;
- ans.push_back(ch);
- }
- return ans;
- }
- string_view skipSpaces(string_view str) {
- int ind = 0;
- int ind2 = str.length();
- while (str[ind] == ' ') ++ind;
- while (str[ind2 - 1] == ' ') --ind2;
- return str.substr(ind, ind2 - ind);
- }
- template <typename Number>
- Number ReadNumberOnLine(istream& stream = cin) {
- Number number;
- stream >> number;
- string dummy;
- getline(stream, dummy);
- return number;
- }
- struct Stop {
- double x = 0, y = 0;
- set<string> buses;
- unordered_map<string, double> dists;
- };
- struct Route {
- string name;
- vector<string> stops;
- int unique_count;
- };
- void readRoute(string_view& str, unordered_map<string, Route>* routes,
- unordered_map<string, Stop>* stops_map) {
- string name(skipSpaces(ReadToken(str, ":")));
- vector<string> stops;
- set<string> s;
- string delimer = (count(str.begin(), str.end(), '>') ? ">" : "-");
- auto stops_sv = split(str, delimer);
- for (auto sv : stops_sv) {
- sv = skipSpaces(sv);
- string stop = string(sv);
- stops.push_back(stop);
- (*stops_map)[stop].buses.insert(name);
- s.insert(stops.back());
- }
- if (delimer == "-") {
- for (int i = stops.size() - 2; i >= 0; --i) {
- stops.push_back(stops[i]);
- }
- }
- (*routes)[name] = { name, stops, int(s.size()) };
- }
- unordered_map<string, double> ReadDists(string_view str) {
- unordered_map<string, double> dists;
- vector<string_view> spliting_dist = split(str, ",");
- for (auto sv : spliting_dist) {
- auto p = SplitTwo(sv, "to");
- string name(skipSpaces(p.second));
- int dist = ConvertToInt(skipSpaces(ReadToken(p.first, "m")));
- dists[name] = dist;
- }
- return dists;
- }
- void readStop(string_view& str, unordered_map<string, Stop>* stops) {
- string name;
- double latitude, longitude;
- name = string(skipSpaces(ReadToken(str, ":")));
- latitude = ConvertToDouble(skipSpaces(ReadToken(str, ",")));
- longitude = ConvertToDouble(skipSpaces(ReadToken(str, ",")));
- unordered_map<string, double> dists = ReadDists(str);
- (*stops)[name].x = latitude;
- (*stops)[name].y = longitude;
- (*stops)[name].dists = move(dists);
- }
- void createDb(unordered_map<string, Stop>* stops,
- unordered_map<string, Route>* routes) {
- int query_count = ReadNumberOnLine<int>();
- string query;
- for (int q_ = 0; q_ < query_count; ++q_) {
- getline(cin, query);
- query = compressSpaces(query);
- string_view str(query);
- string_view pref = skipSpaces(ReadToken(str));
- if (pref == "Bus") {
- readRoute(str, routes, stops);
- }
- else if (pref == "Stop") {
- readStop(str, stops);
- }
- }
- }
- long double calcDist(const Stop& a, const Stop& b, long double R = 6'371'000) {
- long double lhs_lat = a.x * PI / 180;
- long double lhs_lon = a.y * PI / 180;
- long double rhs_lat = b.x * PI / 180;
- long double rhs_lon = b.y * PI / 180;
- return acos(sin(lhs_lat) * sin(rhs_lat) + cos(lhs_lat) * cos(rhs_lat) * cos(abs(lhs_lon - rhs_lon))) * R;
- }
- void getBusAnswer(string_view str,
- unordered_map<string, Stop>* stops_ptr,
- unordered_map<string, Route>* routes) {
- unordered_map<string, Stop>& stops = *stops_ptr;
- string bus(skipSpaces(str));
- if ((*routes).count(bus) == 0) {
- cout << "Bus " << str << ": not found\n";
- return;
- }
- Route& route = (*routes)[bus];
- long double geografical_dist = 0, dist = 0;
- for (int i = 0; i < route.stops.size() - 1; ++i) {
- string& from = route.stops[i];
- string& to = route.stops[i + 1];
- geografical_dist += calcDist(stops[from], stops[to]);
- if (stops[from].dists.count(to)) {
- dist += stops[from].dists[to];
- }
- else {
- dist += stops[to].dists[from];
- }
- }
- long double curvature = dist / geografical_dist;
- cout << "Bus " << str << ": "
- << route.stops.size() << " stops on route, "
- << route.unique_count << " unique stops, "
- << dist << " route length, "
- << curvature << " curvature\n";
- }
- void getStopAnswer(string_view str,
- unordered_map<string, Stop>* stops) {
- string stop(skipSpaces(str));
- cout << "Stop " << stop << ": ";
- if ((*stops).count(stop) == 0) {
- cout << "not found\n";
- return;
- }
- else if ((*stops)[stop].buses.size() == 0) {
- cout << "no buses\n";
- }
- else {
- cout << "buses";
- for (auto& str : (*stops)[stop].buses) {
- cout << " " << str;
- }
- cout << "\n";
- }
- }
- void Proccess(unordered_map<string, Stop>* stops,
- unordered_map<string, Route>* routes) {
- int query_count = ReadNumberOnLine<int>();
- string query;
- for (int q_ = 0; q_ < query_count; ++q_) {
- getline(cin, query);
- query = compressSpaces(query);
- string_view str(query);
- string_view pref = skipSpaces(ReadToken(str));
- if (pref == "Bus") {
- getBusAnswer(str, stops, routes);
- }
- else if (pref == "Stop") {
- getStopAnswer(str, stops);
- }
- }
- }
- int main() {
- cout.fixed;
- cout.precision(8);
- unordered_map<string, Stop> stops;
- unordered_map<string, Route> routes;
- createDb(&stops, &routes);
- Proccess(&stops, &routes);
- }
Advertisement
Add Comment
Please, Sign In to add comment