665 Colaj

[•DITzoneC]

Aici puteţi discuta despre problema Colaj.

[•dudu_valea]

stie pana la urma cineva cum se face problema asta ?

[•wefgef]

Normalizare si fill .

[•Mishu91]

Normalizare si fill .

Si normalizarea asta cu ce se manca? 

[•fireatmyself]

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.         

[•devilkind]

ai grija ca la elemente egale trebuie sa le asociezi aceeasi valoare:

ex:
10000 10000 20000 va deveni
1 1 2

[•Mishu91]

Pai si daca imi numerotez coordonatele cum imi fac fillu?  Pt k eu tre sa fac cu valorile date, sa umplu spatiile goale

[•fireatmyself]

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. 

[•matzipan]

Fillul se poate optimiza pe 2 directii, ca stiva sa nu mai ocupe asa mult.

[•laurion]

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 

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...

[•vladtarniceru]

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

[•elfus]

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.

[•vladtarniceru]

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

[•VisuianMihai]

Problema se rezolva cu niste DFS-uri, doar ca matricea trebuie 'redimensionata'..