Georgiy031

Untitled

Aug 5th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.39 KB | None | 0 0
  1. #define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
  2. #include <bits/stdc++.h>
  3. #include <optional>
  4.  
  5. using namespace std;
  6. const long double PI = 3.1415926535;
  7.  
  8. pair<string_view, optional<string_view>> SplitTwoStrict(string_view s, string_view delimiter = " ") {
  9.     const size_t pos = s.find(delimiter);
  10.     if (pos == s.npos) {
  11.         return { s, nullopt };
  12.     }
  13.     else {
  14.         return { s.substr(0, pos), s.substr(pos + delimiter.length()) };
  15.     }
  16. }
  17. vector<string_view> split(string_view s, string_view delimer = " ") {
  18.     size_t pos = s.find(delimer);
  19.     vector<string_view> ans;
  20.     if (pos == s.npos && s.length()) {
  21.         ans.push_back(s);
  22.     }
  23.     else
  24.         while (pos != s.npos) {
  25.             pos = s.find(delimer);
  26.             ans.push_back(s.substr(0, pos));
  27.             s = s.substr(pos + delimer.length());
  28.         }
  29.     return ans;
  30. }
  31.  
  32. pair<string_view, string_view> SplitTwo(string_view s, string_view delimiter = " ") {
  33.     const auto [lhs, rhs_opt] = SplitTwoStrict(s, delimiter);
  34.     return { lhs, rhs_opt.value_or("") };
  35. }
  36.  
  37. string_view ReadToken(string_view& s, string_view delimiter = " ") {
  38.     const auto [lhs, rhs] = SplitTwo(s, delimiter);
  39.     s = rhs;
  40.     return lhs;
  41. }
  42.  
  43. int ConvertToInt(string_view str) {
  44.     // use std::from_chars when available to git rid of string copy
  45.     size_t pos;
  46.     const int result = stoi(string(str), &pos);
  47.     if (pos != str.length()) {
  48.         std::stringstream error;
  49.         error << "string " << str << " contains " << (str.length() - pos) << " trailing chars";
  50.         throw invalid_argument(error.str());
  51.     }
  52.     return result;
  53. }
  54.  
  55. double ConvertToDouble(string_view str) {
  56.     // use std::from_chars when available to git rid of string copy
  57.     size_t pos;
  58.     const double result = stod(string(str), &pos);
  59.     if (pos != str.length()) {
  60.         std::stringstream error;
  61.         error << "string " << str << " contains " << (str.length() - pos) << " trailing chars";
  62.         throw invalid_argument(error.str());
  63.     }
  64.     return result;
  65. }
  66.  
  67. string compressSpaces(string s) {
  68.     string ans;
  69.     for (auto ch : s) {
  70.         if (ans.size() && ans.back() == ' ' && ch == ' ') continue;
  71.         ans.push_back(ch);
  72.     }
  73.     return ans;
  74. }
  75.  
  76. string_view skipSpaces(string_view str) {
  77.     int ind = 0;
  78.     int ind2 = str.length();
  79.     while (str[ind] == ' ') ++ind;
  80.     while (str[ind2 - 1] == ' ') --ind2;
  81.     return str.substr(ind, ind2 - ind);
  82. }
  83.  
  84. template <typename Number>
  85. Number ReadNumberOnLine(istream& stream = cin) {
  86.     Number number;
  87.     stream >> number;
  88.     string dummy;
  89.     getline(stream, dummy);
  90.     return number;
  91. }
  92.  
  93. struct Stop {
  94.     double x = 0, y = 0;
  95.     set<string> buses;
  96.     unordered_map<string, double> dists;
  97. };
  98.  
  99. struct Route {
  100.     string name;
  101.     vector<string> stops;
  102.     int unique_count;
  103. };
  104.  
  105.  
  106. void readRoute(string_view& str, unordered_map<string, Route>* routes,
  107.     unordered_map<string, Stop>* stops_map) {
  108.     string name(skipSpaces(ReadToken(str, ":")));
  109.     vector<string> stops;
  110.     set<string> s;
  111.     string delimer = (count(str.begin(), str.end(), '>') ? ">" : "-");
  112.     auto stops_sv = split(str, delimer);
  113.     for (auto sv : stops_sv) {
  114.         sv = skipSpaces(sv);
  115.         string stop = string(sv);
  116.         stops.push_back(stop);
  117.         (*stops_map)[stop].buses.insert(name);
  118.         s.insert(stops.back());
  119.     }
  120.     if (delimer == "-") {
  121.         for (int i = stops.size() - 2; i >= 0; --i) {
  122.             stops.push_back(stops[i]);
  123.         }
  124.     }
  125.     (*routes)[name] = { name, stops, int(s.size()) };
  126. }
  127.  
  128. unordered_map<string, double> ReadDists(string_view str) {
  129.     unordered_map<string, double> dists;
  130.     vector<string_view> spliting_dist = split(str, ",");
  131.     for (auto sv : spliting_dist) {
  132.         auto p = SplitTwo(sv, "to");
  133.         string name(skipSpaces(p.second));
  134.         int dist = ConvertToInt(skipSpaces(ReadToken(p.first, "m")));
  135.         dists[name] = dist;
  136.     }
  137.  
  138.     return dists;
  139. }
  140.  
  141. void readStop(string_view& str, unordered_map<string, Stop>* stops) {
  142.     string name;
  143.     double latitude, longitude;
  144.     name = string(skipSpaces(ReadToken(str, ":")));
  145.     latitude = ConvertToDouble(skipSpaces(ReadToken(str, ",")));
  146.     longitude = ConvertToDouble(skipSpaces(ReadToken(str, ",")));
  147.     unordered_map<string, double> dists = ReadDists(str);
  148.     (*stops)[name].x = latitude;
  149.     (*stops)[name].y = longitude;
  150.     (*stops)[name].dists = move(dists);
  151. }
  152.  
  153. void createDb(unordered_map<string, Stop>* stops,
  154.     unordered_map<string, Route>* routes) {
  155.     int query_count = ReadNumberOnLine<int>();
  156.    
  157.     string query;
  158.     for (int q_ = 0; q_ < query_count; ++q_) {
  159.         getline(cin, query);
  160.         query = compressSpaces(query);
  161.         string_view str(query);
  162.         string_view pref = skipSpaces(ReadToken(str));
  163.         if (pref == "Bus") {
  164.             readRoute(str, routes, stops);
  165.         }
  166.         else if (pref == "Stop") {
  167.             readStop(str, stops);
  168.         }
  169.  
  170.     }
  171. }
  172.  
  173. long double calcDist(const Stop& a, const Stop& b, long double R = 6'371'000) {
  174.     long double lhs_lat = a.x * PI / 180;
  175.     long double lhs_lon = a.y * PI / 180;
  176.     long double rhs_lat = b.x * PI / 180;
  177.     long double rhs_lon = b.y * PI / 180;
  178.     return acos(sin(lhs_lat) * sin(rhs_lat) + cos(lhs_lat) * cos(rhs_lat) * cos(abs(lhs_lon - rhs_lon))) * R;
  179. }
  180.  
  181. void getBusAnswer(string_view str,
  182.     unordered_map<string, Stop>* stops_ptr,
  183.     unordered_map<string, Route>* routes) {
  184.    
  185.     unordered_map<string, Stop>& stops = *stops_ptr;
  186.     string bus(skipSpaces(str));
  187.     if ((*routes).count(bus) == 0) {
  188.         cout << "Bus " << str << ": not found\n";
  189.         return;
  190.     }
  191.     Route& route = (*routes)[bus];
  192.     long double geografical_dist = 0, dist = 0;
  193.     for (int i = 0; i < route.stops.size() - 1; ++i) {
  194.         string& from = route.stops[i];
  195.         string& to = route.stops[i + 1];
  196.         geografical_dist += calcDist(stops[from], stops[to]);
  197.        
  198.         if (stops[from].dists.count(to)) {
  199.             dist += stops[from].dists[to];
  200.         }
  201.         else {
  202.             dist += stops[to].dists[from];
  203.         }
  204.     }
  205.     long double curvature = dist / geografical_dist;
  206.     cout << "Bus " << str << ": "
  207.         << route.stops.size() << " stops on route, "
  208.         << route.unique_count << " unique stops, "
  209.         << dist << " route length, "
  210.         << curvature << " curvature\n";
  211. }
  212.  
  213. void getStopAnswer(string_view str,
  214.     unordered_map<string, Stop>* stops) {
  215.  
  216.     string stop(skipSpaces(str));
  217.     cout << "Stop " << stop << ": ";
  218.     if ((*stops).count(stop) == 0) {
  219.         cout << "not found\n";
  220.         return;
  221.     }
  222.     else if ((*stops)[stop].buses.size() == 0) {
  223.         cout << "no buses\n";
  224.     }
  225.     else {
  226.         cout << "buses";
  227.         for (auto& str : (*stops)[stop].buses) {
  228.             cout << " " << str;
  229.         }
  230.         cout << "\n";
  231.     }
  232. }
  233.  
  234. void Proccess(unordered_map<string, Stop>* stops,
  235.     unordered_map<string, Route>* routes) {
  236.  
  237.     int query_count = ReadNumberOnLine<int>();
  238.     string query;
  239.     for (int q_ = 0; q_ < query_count; ++q_) {
  240.         getline(cin, query);
  241.         query = compressSpaces(query);
  242.         string_view str(query);
  243.         string_view pref = skipSpaces(ReadToken(str));
  244.         if (pref == "Bus") {
  245.             getBusAnswer(str, stops, routes);
  246.         }
  247.         else if (pref == "Stop") {
  248.             getStopAnswer(str, stops);
  249.         }
  250.  
  251.     }  
  252.  
  253. }
  254.  
  255. int main() {
  256.     cout.fixed;
  257.     cout.precision(8);
  258.     unordered_map<string, Stop> stops;
  259.     unordered_map<string, Route> routes;
  260.     createDb(&stops, &routes);
  261.     Proccess(&stops, &routes);
  262. }
  263.  
Advertisement
Add Comment
Please, Sign In to add comment