Se consideră n puncte colorate dispuse în plan. Ele sunt identificate prin coordonatele lor întregi, pe axele OX și OY. Fiecare punct are asociat un număr natural între 1 și C reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoare condiții:

toate cele patru vârfuri se regăsesc printre cele n puncte date;
are laturile paralele cu axele OX, OY;
are vârfurile colorate în aceeași culoare.

Cerința

Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele n puncte din plan.

Date de intrare

Pe prima linie a fișierului text dreptc.in se găsesc două numere n maxc reprezentând numărul de puncte din plan și numărul de culori asociate punctelor. Pe următoarele n linii se citesc câte trei numere x y c reprezentând în ordine coordonata pe axa OX (abscisa), coordonata pe axa OY (ordonata) și codul culorii asociate punctului. Nu există două puncte cu aceleași coordonate.

Date de ieșire

Fișierul de ieșire dreptc.out va conține un singur număr reprezentând numărul maxim de dreptunghiuri corecte.

Restricții și precizări

1 ≤ N ≤ 1000
1 ≤ C ≤ 5
-1000 ≤ x , y ≤ 1000
40% din teste vor avea N ≤ 100

Exemplu

dreptc.in

dreptc.out

Explicație

Vârfurile celor trei dreptunghiuri corecte sunt:
(3,0) (3,4) (6,4) (6,0)
(3,0) (3,10) (6,10) (6,0)
(3,6) (3,10) (6,10) (6,4).

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

#include <bits/stdc++.h>

using namespace std;

int n, c;
int cnt;

vector< pair<int,int> > v[2005];

void Read()
{
    int i, x, y, k;
    ifstream fin("dreptc.in");

    fin >> n;
    fin >> c;

    for(i = 1; i <= n; i++)
    {
        fin >> x >> y >> k;
        x += 1000;
        y += 1000;
        v[x].push_back({y, k});
    }
    fin.close();
}

void Contor(int L1, int L2)
{
    int i, j, N, M;
    int color[6];
    for (i = 1; i <= c; i++)
        color[i] = 0;
    N = v[L1].size();
    M = v[L2].size();
    i = j = 0;
    while (i < N && j < M)
    {
        if (v[L1][i].first < v[L2][j].first)
            i++;
        else if (v[L1][i].first > v[L2][j].first)
            j++;
        else
        {
            if (v[L1][i].second == v[L2][j].second)
                color[v[L1][i].second]++;
            i++; j++;
        }
    }
    for (i = 1; i <= c; i++)
        if (color[i] > 1)
            cnt += (color[i]*(color[i]-1)/2);
}

void Rezolvare()
{
    int i, L1, L2;
    for (i = 0; i <= 2000; i++)
        if (v[i].size() > 0)
            sort(v[i].begin(), v[i].end());
    cnt = 0;
    for (L1 = 0; L1 < 2000; L1++)
       if (v[L1].size() > 0)
         for (L2 = L1 + 1; L2 <= 2000; L2++)
            if (v[L2].size() > 0)
                Contor(L1, L2);
    ofstream fout("dreptc.out");
    fout << cnt << "\n";
    fout.close();
}

int main()
{
    Read();
    Rezolvare();
    return 0;
}

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 #2170 dreptc

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