Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- bool kuhnAlgorithm(int u, vector<bool> &used, vector<vector<int>> &g, vector<int> &part1) {
- if (used[u]) {
- return false;
- }
- used[u] = true;
- for (int const &v : g[u]) {
- if (part1[v] == -1 || kuhnAlgorithm(part1[v], used, g, part1)) {
- part1[v] = u;
- return true;
- }
- }
- return false;
- }
- struct Event {
- int time;
- int x;
- int y;
- Event(int time, int x, int y) {
- this->time = time;
- this->x = x;
- this->y = y;
- }
- };
- double dist(int x1, int y1, int x2, int y2) {
- return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
- }
- int main() {
- freopen("ufo.in", "r", stdin);
- freopen("ufo.out", "w", stdout);
- int n;
- int v;
- cin >> n >> v;
- vector<Event> events;
- for (int i = 0; i < n; ++i) {
- string s;
- cin >> s;
- int x;
- int y;
- cin >> x >> y;
- events.push_back(Event(stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)), x, y));
- }
- sort(events.begin(), events.end(), [](Event x, Event y) {
- return x.time < y.time;
- });
- vector<vector<int>> g(n + n + 1);
- double eps = 0.000001;
- for (int i = 0; i < n; ++i) {
- for (int j = i + 1; j < n; ++j) {
- if (dist(events[i].x, events[i].y, events[j].x, events[j].y) / (1.0 * v) -
- (events[j].time - events[i].time) / 60.0 <= eps) {
- g[i + 1].push_back(j + n + 1);
- g[j + n + 1].push_back(i + 1);
- }
- }
- }
- vector<int> part1(n + n + 1, -1);
- for (int i = 1; i <= n; ++i) {
- vector<bool> used(n + n + 1, false);
- kuhnAlgorithm(i, used, g, part1);
- }
- int cnt = 0;
- for (int i = n + 1; i <= n + n; ++i) {
- cnt += (int) (part1[i] != -1);
- }
- cout << (cnt == 0 ? n : cnt) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement