Cod sursa(job #2791268)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 30 octombrie 2021 12:08:22
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n, m, rez;
vector < pair <int, int> > v;
pair <int, int> rat[1005], zid[1005];

void input() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> rat[i].first >> rat[i].second;
    fin >> m;
    for (int i = 1; i <= m; ++i)
        fin >> zid[i].first >> zid[i].second;
    return;
}

void solve() {
    sort(zid + 1, zid + m + 1);
    for (int i = 1; i <= n; ++i) {
        int x = rat[i].first, y = rat[i].second, s = 0;
        for (int j = 1; j <= m; ++j)
            if (zid[j].first < x)
                s = j;
        if (s < m && zid[s + 1].first > x && s > 0) {gps
            
            v.push_back({zid[s].first + 1, 1});
            v.push_back({zid[s + 1].first, -1});
        }
        if (s == m) {
            v.push_back({zid[s].first + 1, 1});
            v.push_back({1e9 + 1, -1});
        }
        if (s == 0) {
            v.push_back({1, 1});
            v.push_back({zid[1].first, -1});
        }
        int pos = x;
        for (int j = s; j >= 1; --j) {
            int a = zid[j].first, b = zid[j].second;
            if (b >= y)
                break;
            double dx = x - a, dy = y - b;
            int nr = 1;
            if (dx != 0)
                nr = ceil((double)b / (dy / dx));
            pos = min(pos, a - nr);
            if (pos < 1)
                break;
            if ((j == 1 && pos >= 1) || pos > zid[j - 1].first) {
                v.push_back({(j == 1 ? 1 : zid[j - 1].first + 1), 1});
                v.push_back({pos + 1, -1});
            }
        }
        pos = x;
        if (s > 0 && zid[s].first == x)
            --s;
        for (int j = s + 1; j <= m; ++j) {
            int a = zid[j].first, b = zid[j].second;
            if (b >= y)
                break;
            double dx = a - x, dy = y - b;
            int nr = 1;
            if (dx != 0)
                nr = ceil((double)b / (dy / dx));
            pos = max(pos, a + nr);
            if (pos > 1e9)
                break;
            if ((j == m && pos <= 1e9) || pos < zid[j + 1].first) {
                v.push_back({pos, 1});
                v.push_back({(j == m ? 1e9 + 1 : zid[j + 1].first), -1});
            }
        }
    }
    sort(v.begin(), v.end());
    int aux = 0, rezf = 0;
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i].first << " " << v[i].second << '\n';
        aux += v[i].second;
        rezf = max(rezf, aux);
    }
    fout << rezf;
    return;
}

int main() {
    input();
    solve();
    return 0;
}