În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze rațe în orașul său preferat, Craiova. Se știe că există N rațe reprezentate prin puncte în planul de coordonate xOy, având coordonatele (x,y) și M ziduri sub forma unor segmente verticale având un capăt pe axa Ox și o anumită înălţime fiecare.

Vânătorul Elmer dorește să împuște cât mai multe rațe. El poate fi poziționat în orice punct de abscisă număr natural nenul, pe axa Ox. O rață poate fi ochită de vânător dacă zidul nu blochează glonțul vânătorului, adică segmentul imaginar delimitat de rață și de vânător nu se intersectează cu nici un zid.

Cerința

Să se afle numărul maxim de rațe care pot fi ochite de vânătorul Elmer.

Date de intrare

Fișierul de intrare elmer.in conține pe prima linie numărul natural N, reprezentând numărul de rațe. Pe următoarele N linii se află perechi de numere naturale, reprezentând coordonatele rațelor. Pe următoarea linie se află numărul natural M, reprezentând numărul de ziduri, iar pe următoarele M linii, perechi de numere naturale, reprezentând abscisa și înălțimea fiecărui zid.

Date de ieșire

Fișierul de ieșire elmer.out va conține pe prima linie numărul maxim de rațe care pot fi ochite de Elmer.

Restricții și precizări

1 ≤ N, M ≤ 1 000
Coordonatele rațelor și ale zidurilor, precum și înălțimile zidurilor sunt din intervalul [1,1 000 000 000]
Se consideră numai coordonate întregi pozitive pentru vânător care nu corespund cu coordonatele niciunui zid.
Dacă glonțul trece prin vârful unui zid, se consideră că poate trece de el.
Se garantează că nu există ziduri cu aceeași abscisa, nici rațe aflate la aceleași coordonate și nici rațe care să fie “în zid” (adică nici o rață nu se afla pe segmentul închis delimitat de capetele unui zid).
Pentru 15% din teste, se garantează faptul că 1 ≤ N, M ≤ 50 și vânătorului îi este suficient să se poziționeze în intervalul [1,1 000] pentru a putea împușca numărul maxim de rațe.
Pentru alte 25% din teste, se garantează doar faptul că 1 ≤ N, M ≤ 50.

Exemplul 1

elmer.in

elmer.out

Exemplul 2

elmer.in

elmer.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Elmer:

// Popoveniuc Mircea - O((N*M)*log(N*M)) - 100p
#include<bits/stdc++.h>

using namespace std;

typedef long long int lld;
typedef pair<lld, lld> Point;
const lld INF = (1LL << 60) - 1;
const lld NMAX = 1e3;
const lld MMAX = 1e3;

void read();
void solve();
void print();

int N, M, sol;
vector<Point> ducks;
vector<Point> walls;
vector<Point> E;

struct eventCmp {
    bool operator()(const Point& e1, const Point &e2) const {
        if (e1.first == e2.first)
            return e1.second > e2.second;
        return e1.first < e2.first;
    }
};

lld cp(Point& A, Point& B, Point& C) {
    return (A.first - C.first) * 1LL * (B.second - C.second) - (A.second - C.second) * 1LL * (B.first - C.first);
}

lld find_min_pos(Point& duck, vector<Point>& S) {
    if (duck.second <= S[0].second)
        return INF;
    double x = (S[0].first * 1LL * duck.second - duck.first * 1LL * S[0].second) * 1.0 / (duck.second - S[0].second);
    return (fabs(x) - (lld)x <= 1e-6) ? x : x + 1.0;
}

lld find_max_pos(Point& duck, vector<Point>& S) {
    if (duck.second <= S[0].second)
        return -INF;
    double x = (S[0].first * 1LL * duck.second - duck.first * 1LL * S[0].second) * 1.0 / (duck.second - S[0].second);
    return x;
}

int main() {
    freopen("elmer.in", "r", stdin);
    freopen("elmer.out", "w", stdout);

    read();
    solve();
    print();

    return 0;
}

void read() {
    scanf("%d", &N);

    assert(1 <= N && N <= 1000);

    for (int i = 1, x, y; i <= N; i++) {
        scanf("%d%d", &x, &y);
        assert(1 <= x && x <= 1000000000);
        assert(1 <= y && y <= 1000000000);
        ducks.push_back(make_pair(x, y));
    }

    walls.push_back(make_pair(0, 0));

    scanf("%d", &M);

    assert(1 <= M && M <= 1000);

    for (int i = 1, x, h; i <= M; i++) {
        scanf("%d%d", &x, &h);
        assert(1 <= x && x <= 1000000000);
        assert(1 <= h && h <= 1000000000);
        walls.push_back(make_pair(x, h));
    }

    M += 2;

    walls.push_back(make_pair(INF, 0));
}

void solve() {
    lld L[NMAX + 5];
    lld R[NMAX + 5];

    sort(ducks.begin(), ducks.end());
    sort(walls.begin(), walls.end());

    for (int i = 0; i < N; i++) {
        Point duck = ducks[i];

        int lb = (int)(lower_bound(walls.begin(), walls.end(), duck) - walls.begin());
        vector<Point> S;

        for (int j = lb; j < M; j++) {
            Point wall = walls[j];

            while (!S.empty() && cp(duck, S.back(), wall) >= 0)
                S.pop_back();
            S.push_back(wall);

            L[j] = find_min_pos(duck, S);
            R[j] = INF - 1;
        }

        S.clear();

        for (int j = lb - 1; j >= 0; j--) {
            Point wall = walls[j];

            while (!S.empty() && cp(duck, S.back(), wall) <= 0)
                S.pop_back();
            S.push_back(wall);

            L[j] = -INF + 1;
            R[j] = find_max_pos(duck, S);
        }

        for (int j = 0; j + 1 < M; j++) {
            lld l, r;

            l = max(walls[j].first + 1LL, L[j]);
            r = min(walls[j + 1].first - 1LL, R[j + 1]);

            if (l <= r) {
                E.push_back(make_pair(l, 1));
                E.push_back(make_pair(r, -1));
            }
        }
    }

    sort(E.begin(), E.end(), eventCmp());

    int hit = 0;

    for (auto event = E.begin(); event != E.end(); event++) {
        hit += event->second;
        sol = max(sol, hit);
    }
}

void print() {
    printf("%d\n", sol);
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1676 Elmer

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1676 Elmer de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1676 Elmer