Advertisement
Guest User

Untitled

a guest
Feb 16th, 2020
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. bool kuhnAlgorithm(int u, vector<bool> &used, vector<vector<int>> &g, vector<int> &part1) {
  9.     if (used[u]) {
  10.         return false;
  11.     }
  12.  
  13.     used[u] = true;
  14.     for (int const &v : g[u]) {
  15.         if (part1[v] == -1 || kuhnAlgorithm(part1[v], used, g, part1)) {
  16.             part1[v] = u;
  17.  
  18.             return true;
  19.         }
  20.     }
  21.  
  22.     return false;
  23. }
  24.  
  25. struct Event {
  26.     int time;
  27.     int x;
  28.     int y;
  29.  
  30.     Event(int time, int x, int y) {
  31.         this->time = time;
  32.         this->x = x;
  33.         this->y = y;
  34.     }
  35. };
  36.  
  37. double dist(int x1, int y1, int x2, int y2) {
  38.     return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
  39. }
  40.  
  41. int main() {
  42.     freopen("ufo.in", "r", stdin);
  43.     freopen("ufo.out", "w", stdout);
  44.    
  45.     int n;
  46.     int v;
  47.     cin >> n >> v;
  48.  
  49.     vector<Event> events;
  50.     for (int i = 0; i < n; ++i) {
  51.         string s;
  52.         cin >> s;
  53.  
  54.         int x;
  55.         int y;
  56.         cin >> x >> y;
  57.  
  58.         events.push_back(Event(stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)), x, y));
  59.     }
  60.    
  61.     sort(events.begin(), events.end(), [](Event x, Event y) {
  62.         return x.time < y.time;
  63.     });
  64.  
  65.     vector<vector<int>> g(n + n + 1);
  66.     double eps = 0.000001;
  67.     for (int i = 0; i < n; ++i) {
  68.         for (int j = i + 1; j < n; ++j) {
  69.             if (dist(events[i].x, events[i].y, events[j].x, events[j].y) / (1.0 * v) -
  70.                 (events[j].time - events[i].time) / 60.0 <= eps) {
  71.                 g[i + 1].push_back(j + n + 1);
  72.                 g[j + n + 1].push_back(i + 1);
  73.             }
  74.         }
  75.     }
  76.  
  77.     vector<int> part1(n + n + 1, -1);
  78.  
  79.     for (int i = 1; i <= n; ++i) {
  80.         vector<bool> used(n + n + 1, false);
  81.         kuhnAlgorithm(i, used, g, part1);
  82.     }
  83.  
  84.     int cnt = 0;
  85.     for (int i = n + 1; i <= n + n; ++i) {
  86.         cnt += (int) (part1[i] != -1);
  87.     }
  88.  
  89.     cout << (cnt == 0 ? n : cnt) << endl;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement