Ben are un teren pe care se află o pădure cu arbori seculari. Acolo vrea să-şi construiască o cabană, însă el fiind ecologist nu vrea să taie niciun arbore, ci vrea să găsească cea mai mare suprafaţă dreptunghiulară fără arbori. El caută o suprafaţă dreptunghiulară străjuită doar în colţuri de arbori şi cu laturile paralele cu axele de coordonate. Ben cunoaşte coordonatele tuturor arborilor din pădure şi vă roagă să-l ajutaţi să găsească aria dreptunghiului cu suprafaţă maximă care are arbori doar în cele patru colțuri.

Cerința

Cunoscând numărul arborilor din pădure şi coordonatele acestora, se cere să se determine aria dreptunghiului de suprafaţă maximă cu copaci doar în cele 4 colţuri, unde Ben intenţionează să-şi construiască cabana.

Date de intrare

Fișierul de intrare cabana.in conține pe prima linie un număr natural n, reprezentând numărul de arbori din pădure. Pe fiecare dintre următoarele n linii se află două numere întregi, separate printr-un spațiu, ce reprezintă abscisa și ordonata unui arbore.

Date de ieșire

Fișierul de ieșire cabana.out va conține pe prima linie pe prima linie numărul natural a, reprezentând aria dreptunghiului de suprafață maximă.

Restricții și precizări

Pentru 10% din teste: 1 ≤ n ≤ 10, -10^3 ≤ x ≤ 10^3, -10^3 ≤ y ≤ 10^3
Pentru 30% din teste: 1 ≤ n ≤ 500, -10^3 ≤ x ≤ 10^3, -10^3 ≤ y ≤ 10^3
Pentru 50% din teste: 1 ≤ n ≤ 500, -10^6 ≤ x ≤ 10^6, -10^6 ≤ y ≤ 10^6
Pentru 70% din teste: 1 ≤ n ≤ 3000, -10^9 ≤ x ≤ 10^9, -10^9 ≤ y ≤ 10^9
Pentru 100% din teste: 1 ≤ n ≤ 50000, -10^9 ≤ x ≤ 10^9, -10^9 ≤ y ≤ 10^9
Nu există doi arbori așezați pe aceeași poziție.

Exemplu

cabana.in

cabana.out

Explicație

Coordonatele dreptunghiului de arie maximă cu laturile paralele cu axele de coordonate şi care nu conţine arbori decât în colţuri sunt:

19 19
29 19
29 4
19 4

deci aria maximă este 150.

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 Cabana:

// student MIhai Nitu - Universitatea Bucuresti

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

#define maxn 150010
#define inf 1000000001

using namespace std;

ifstream fin ("cabana.in");
ofstream fout("cabana.out");

struct point
{
    int x,y,i;
}v[maxn], v1[maxn], v2[maxn];

bool cmp1 (point a, point b)
{
    if (a.x == b.x)
        return a.y > b.y;
    return a.x < b.x;
}

bool cmp2 (point a, point b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y > b.y;
}

int bit[maxn], whichL[maxn], whichC[maxn], posL[maxn], posC[maxn], pointer[maxn];
int sq, p, nr1, nr2, t, n;
vector<int> C[maxn], L[maxn];

void create_structure()
{
    sq = sqrt(nr1);

    v[0].y = -inf;
    int maxpoint = 0;
    t = 0;

    for (int i = 1; i <= nr1; ++i)
    {
        if (v[C[i][0]].y > v[maxpoint].y)
            maxpoint = C[i][0];

        if (i % sq == 0)
        {
            ++t;
            bit[t] = maxpoint;
            maxpoint = 0;
        }
    }
}

void update (int pos)
{
    int whbit = (pos-1)/sq+1;

    if (whbit > t)
        return;

    int maxpoint = 0;

    for (int i = (whbit-1)*sq + 1; i <= whbit*sq; ++i)
    {
        if (v[C[i][pointer[i]]].y > v[maxpoint].y)
            maxpoint = C[i][pointer[i]];
    }

    bit[whbit] = maxpoint;
}

int query (int left, int right)
{
    int maxpoint = 0;

    if (right - left + 1 <= sq)
    {
        for (int i = left; i <= right; ++i)
        {
            if (v[C[i][pointer[i]]].y > v[maxpoint].y)
            {
                maxpoint = C[i][pointer[i]];
            }
        }

        p = whichC[maxpoint];
        return v[maxpoint].y;
    }

    int whleft = (left-1)/sq+1;
    int whright = (right-1)/sq+1;

    for (int i = whleft+1; i <= whright-1; ++i)
    {
        if (v[bit[i]].y > v[maxpoint].y)
            maxpoint = bit[i];
    }

    for (int i = left; i <= whleft*sq; ++i)
    {
        if (v[C[i][pointer[i]]].y > v[maxpoint].y)
        {
            maxpoint = C[i][pointer[i]];
        }
    }

    for (int i = (whright-1)*sq +1; i <= right; ++i)
    {
        if (v[C[i][pointer[i]]].y > v[maxpoint].y)
        {
            maxpoint = C[i][pointer[i]];
        }
    }

    p = whichC[maxpoint];
    return v[maxpoint].y;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        v1[i].x = v[i].x;
        v1[i].y = v[i].y;
        v2[i].x = v[i].x;
        v2[i].y = v[i].y;
        v1[i].i = i;
        v2[i].i = i;
    }

    sort(v1+1, v1+n+1, cmp1);
    sort(v2+1, v2+n+1, cmp2);

    v1[0].x = -inf;

    for (int i=1 ; i <= n; ++i)
    {
        if (v1[i].x != v1[i-1].x)
        {
            ++nr1;
        }
        C[nr1].push_back(v1[i].i);
        whichC[v1[i].i] = nr1;
        posC[v1[i].i] = C[nr1].size()-1;
    }

    v2[0].y = inf;

    for (int i =1 ; i <= n; ++i)
    {
        if (v2[i].y != v2[i-1].y)
        {
            ++nr2;
        }

        L[nr2].push_back(v2[i].i);
        whichL[v2[i].i] = nr2;
        posL[v2[i].i] = L[nr2].size()-1;
    }

    for (int i = 1; i <= nr1; ++i)
    {
        pointer[i] = 0;
        C[i].push_back(0);
    }

    create_structure();
    long long answer = 0;

    int cnt = 0;

    while (query(1,nr1) != -inf)
    {
        ++cnt;
        point LU = v[C[p][pointer[p]]];
        int whcol = p;
        int poscol = pointer[p];
        int whline = whichL[C[p][pointer[p]]];
        int posline = posL[C[p][pointer[p]]];

        if (posline + 1 < L[whline].size() && poscol + 1 < C[whcol].size()-1)
        {
            int rightp = L[whline][posline+1];
            int downp = C[whcol][poscol+1];

            point RU = v[rightp];
            point LD = v[downp];

            int newcol = whichC[rightp];
            int posnewcol = posC[rightp];
            int newline = whichL[downp];
            int posnewline = posL[downp];

            if (posnewcol + 1 < C[newcol].size()-1 && posnewline + 1 < L[newline].size() && C[newcol][posnewcol+1] == L[newline][posnewline+1])
            {
                point RD = v[C[newcol][posnewcol+1]];

                int rez = query(whcol+1, newcol-1);

                if (rez < RD.y)
                {
                    answer = max(answer, 1LL*(RD.x - LD.x)*(RU.y - RD.y));
                }
            }
        }

        ++pointer[whcol];
        update(whcol);
    }

    fout << answer;
}

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 #1193 Cabana

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1193 Cabana 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 #1193 Cabana