infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 18, 2008, 11:47:24



Titlul: 665 Colaj
Scris de: Adrian Diaconu din Martie 18, 2008, 11:47:24
Aici puteţi discuta despre problema Colaj (http://infoarena.ro/problema/colaj).


Titlul: Răspuns: 665 Colaj
Scris de: dumitrache-valea andrei din Martie 24, 2008, 17:06:53
stie pana la urma cineva cum se face problema asta ?


Titlul: Răspuns: 665 Colaj
Scris de: Andrei Grigorean din Martie 24, 2008, 20:59:42
Normalizare si fill :).


Titlul: Răspuns: 665 Colaj
Scris de: Andrei Misarca din Aprilie 01, 2008, 20:58:13
Normalizare si fill :).
Si normalizarea asta cu ce se manca?  :?


Titlul: Răspuns: 665 Colaj
Scris de: Bogdan-Alexandru Stoica din Aprilie 02, 2008, 10:31:24
sa zicem ca ai niste puncte pe axa Ox, coordonatele absciselor fiind intre 1 miliard si 2 miliarde. daca in algoritmul tau nu folosesti nicaieri valorile coordonatelor, ci doar ordinea lor, poti sa faci urmatoarea preprocesare: sortezi punctele crescator si asociezi fiecaruia pozitia lui in sortare. se observa usor ca aceasta renumerotare pastreaza relatiile ordinea intre puncte.

de exemplu ai punctele: 1234567890, 1000100123, 1000000000 si 2000000000.
ordonate crescator sirul devine: 1000000000, 1000100123, 1234567890 si 2000000000.
vom renumerota sirul:                      1                 2               3         si         4.         


Titlul: Răspuns: 665 Colaj
Scris de: Savin Tiberiu din Aprilie 02, 2008, 10:46:00
ai grija ca la elemente egale trebuie sa le asociezi aceeasi valoare:

ex:
10000 10000 20000 va deveni
1 1 2


Titlul: Răspuns: 665 Colaj
Scris de: Andrei Misarca din Aprilie 02, 2008, 13:28:58
Pai si daca imi numerotez coordonatele cum imi fac fillu?  :fool: Pt k eu tre sa fac cu valorile date, sa umplu spatiile goale


Titlul: Răspuns: 665 Colaj
Scris de: Bogdan-Alexandru Stoica din Aprilie 02, 2008, 14:40:48
normalizezi pe componente (intai abscisele, apoi ordonatele).
sortezi abscisele si construiesti vectorul new_coord in care retii noile abscise ale punctelor. am ajuns la pasul i. daca abscisa i-1 si abscisa i sunt egale atunci exista o sansa ca dreptunghiurile deservite de acestea sa se intersecteze, deci in matricea ta ar trebui sa apara ca o zona continua. prin urmare le vei atribui coordonate consecuvite (new_coord[ i ] = new_coord[i-1]+1). in caz contrar, cele doua dreptunghiuri nu se vor intersecta niciodata si trebuie sa evidentiezi acest lucru in matricea ta, despartindu-le printr-o linie, deci new_coord[ i ] = new_coord[i-1]+2.
analog pentru ordonate.

daca folosesti o matrice de 200x200 de tip char ar trebui sa nu ai probleme cu memoria.

nu am implementat acest lucru sa vad ca merge, dar pare ok. imi cer scuze anticipat, daca am omis vreun caz.  :D


Titlul: Răspuns: 665 Colaj
Scris de: Andrei din Martie 05, 2010, 00:18:00
Fillul se poate optimiza pe 2 directii, ca stiva sa nu mai ocupe asa mult.


Titlul: Răspuns: 665 Colaj
Scris de: Laurentiu Ion din Martie 16, 2011, 12:06:02
Nu inteleg de ce pica 4 teste cu Incorect  ](*,) ](*,) Normalizez matricea sortand abscisele si ordonatele... Daca ati putea sa va uitati sa imi spuneti unde gresesc ar fii super  :thumbup: :thumbup:

Cod:
#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
using namespace std;

const int   dx[]={0,1,0,-1},
            dy[]={1,0,-1,0};

int lenX,lenY;
bool a[210][210];

struct dreptunghi
{
int absc1,ord1;
int absc2,ord2;

};
struct punct
{
    int val,dr;
    bool first;
};
inline bool cmp(punct a, punct b)
{
    return a.val<b.val;
}
inline void fill(int i,int j)
{
    if(i<0 || i>=lenX || j<0 || j>=lenY)
        return;
    a[i][j]=1;
    for(int k=0;k<4;++k)
    {
        if(a[i+dx[k]][j+dy[k]]==0)
        {
            fill(i+dx[k],j+dy[k]);
        }
    }
}
int main()
{
std::ifstream fin("colaj.in");
std::ofstream fout("colaj.out");

dreptunghi dr[120];
    punct X[220],Y[220];


int n,m,p;
fin>>n>>m>>p;

    int i,j,j1,j2;
    int x0=0,y0=0;
    int nx=1,ny=1;
for(i=0;i<n;++i)
{
    fin>>dr[i].absc1>>dr[i].ord1>>dr[i].absc2>>dr[i].ord2;

    if(dr[i].absc1==0) x0=1;
    if(dr[i].ord1==0) y0=1;

    if(dr[i].absc2==m) nx=0;
    if(dr[i].ord2==p) ny=0;

    X[i<<1].val=dr[i].absc1;
        X[(i<<1)+1].val=dr[i].absc2;

    X[i<<1].first=true;
    X[(i<<1)+1].first=false;

    X[i<<1].dr=i;
    X[(i<<1)+1].dr=i;


    Y[i<<1].val=dr[i].ord1;
        Y[(i<<1)+1].val=dr[i].ord2;

    Y[i<<1].first=true;
    Y[(i<<1)+1].first=false;

    Y[i<<1].dr=i;
    Y[(i<<1)+1].dr=i;
}



    lenX=n<<1;

std::sort(X,X+lenX,cmp);


    int new_coord=x0;
//    new_coord=t;
    if(X[0].first)
        dr[X[0].dr].absc1=new_coord;
    else
        dr[X[0].dr].absc2=new_coord;
for(i=1;i<lenX;++i)
{
    if(X[i].val!=X[i-1].val)
    {
        ++new_coord;
        }
        if(X[i].first)
            dr[X[i].dr].absc1=new_coord;
        else
            dr[X[i].dr].absc2=new_coord;
}

    lenX=new_coord+1+nx;


    lenY=n<<1;

sort(Y,Y+lenY,cmp);


    new_coord=y0;

    if(Y[0].first)
        dr[Y[0].dr].ord1=new_coord;
    else
        dr[Y[0].dr].ord2=new_coord;
for(i=1;i<lenY;++i)
{
    if(Y[i].val!=Y[i-1].val)
    {
        ++new_coord;
        }
        if(Y[i].first)
            dr[Y[i].dr].ord1=new_coord;
        else
            dr[Y[i].dr].ord2=new_coord;
}

    lenY=new_coord+1+ny;




    memset(a,0,sizeof(a));

    for(i=0;i<n;++i)
    {
        for(j1=dr[i].ord1;j1<dr[i].ord2;++j1)
            for(j2=dr[i].absc1;j2<dr[i].absc2;++j2)
                a[j1][j2]=1;
    }
    int rez=0;


    for(i=0;i<lenX;++i)
    {
        for(j=0;j<lenY;++j)
        {
            if(a[i][j]==0)
            {
                fill(i,j);
                ++rez;
            }
        }
    }




    fout<<rez<<'\n';



return 0;
}

PS: Nu sunt sigur ca e bine sa las sursa aici dar nu stiu cum sa intreb altfel...


Titlul: Răspuns: 665 Colaj
Scris de: Vlad Tarniceru din Aprilie 28, 2011, 18:03:24
si eu iau la fel incorect pe 4 teste, cred ca e ceva legat de linia si coloana 0 dar am facut si asa si iau ori 30 ori 60
are cineva idee de la ce ar putea fi? :?
multumesc :)


Titlul: Răspuns: 665 Colaj
Scris de: Florin Chirica din Aprilie 28, 2011, 18:57:00
Vad ca ai incorect pe aceleasi teste pe care le am si eu. Daca descoperi unde-i greseala te rog sa postezi aici, cred ca avem aceeasi greseala.


Titlul: Răspuns: 665 Colaj
Scris de: Vlad Tarniceru din Aprilie 29, 2011, 18:34:42
am descoperit, afiseaza matricea care se formeaza din exemplu si incearca sa-ti dai seama ce nu e bine pentru al treilea dreptunghi (o sa vezi ca al treilea dreptunghi nu-l pune bine si lasa loc liber sub el (poate nu in exemplu, dar asta era gresit la mine))

si daca nu-ti dai seama uite unde trebuie sa cauti eroarea:
incearca sa vezi cand ai dreptunghiuri care se lipesc de o margine (nu marginile cu 0, marginile cu n si p) :)

bafta :D


Titlul: Răspuns: 665 Colaj
Scris de: Mihai Visuian din Iunie 22, 2012, 13:34:13
Problema se rezolva cu niste DFS-uri, doar ca matricea trebuie 'redimensionata'..