567 Flori2

[•DITzoneC]

Aici puteţi discuta despre problema Flori2.

[•bogdanhm999]

 c tip de sortare sau ce functie de aflare a unghilui ati folosit k mie imi iese din timp cu mai multe variante ?

[•wefgef]

Eu am sortat cu sort-ul din STL dupa functia atan2.

[•bogdanhm999]

am facut cum ai zis intra sub 1.4 sec dar da incorect.....m-am uitat si la solutie am facut ca acolo cu o precizie de 10^(-9) ....si altele...nush ce are de nu mere....poate un test cv mai complex daca poti sa imi dai k aglomerez degeaba evaluatoru 

[•wefgef]

Eu am facut cu precizie de 10^-10

[•DraStiK]

ma ajuta cineva si pe mine?

eu icnerc sa fac altfel: pentru fiecare punct i aflu panta celorlalte puncte cu acesta - imi formez segmente cu un capat in punctul i si celalat in j si verifica apoi pentru fiecare punct i nr maxim de pante egale, dupa ce sortez

e gresit ceva in gandirea asta?

[•wefgef]

E buna ideea ta. M-am uitat peste codul tau si am gasit niste greseli:

Cod:

void check ()
{
    int i,nr;
    for (i=1; i<=m; ++i)
        // greseala 1: nu verifici daca i < m; alternativ ai putea sa faci forul doar pana cand i < m
        if (i < m && abs (a[i]-a[i+1])<0.00000001)
        {
            nr=1;
            // greseala 2: initial aveai la sfarsitul conditiei din while i < n
            while (abs (a[i]-a[i+1])<0.00000000001 && i<m)
            {
                ++i;
                ++nr;
            }
            if (nr>nmax)
                nmax=nr;
        }
}

Cu aceste doua modificari, vei obtine 100 de puncte.

[•DraStiK]

multumesc de ajutor
a iesit

[•andrici_cezar]

Am facut un program care cauta in matrice elemente vecine

Cod:

#include<fstream.h>

long long a[1001],b[1001],x,y,i,l,n,k,lm,t,j;
int main()

{

ifstream f("flori2.in");
ofstream g("flori2.out");
f>>t;
for(i=1;i<=t;i++)
	{
	lm=0;
	f>>n;
	for(j=1;j<=n;j++)
	    f>>a[j]>>b[j];
	//in sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
	       if ((x-1==a[k])&&(y==b[k]))
			{
			l++;
			x=a[k];
			}
	   if (l>lm) lm=l;
	   }
	//in jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y==b[k]))
			{
			l++;
			x=a[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala stanga jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y-1==b[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala stanga sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x-1==a[k])&&(y-1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala dreapta jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y+1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala dreapta sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x-1==a[k])&&(y+1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//dreapta
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x==a[k])&&(y-1==a[k]))
			{
			l++;
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//stanga
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x==a[k])&&(y+1==a[k]))
			{
			l++;
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	g<<lm;
	g<<'\n';
	}
f.close();
g.close();
return 0;
}

e cel mai banal mod de a cauta si nici nu iese din timp, adica pentru 11 teste si cate 1000 de flori pentru fiecare test face in total 88.008.000 de operatii deci e foarte putin se incadreaza in timp, dar zicetimi ce e gresit va rog

[...]

Am gasit greseala

[•Bogdan_tmm]

Puteti sa-mi lasati si mie niste teste? Ca pe ce am incercat eu imi merge algoritmul dar se incadreaza la limita. Si cand se incadreaza imi da WA(ca sa intre in timp folosesc stable_sort din stl )
Problema e ca fac N (N+NlogN+N).Dar pentru a lua pe rand punctele mie imi mai trebuie un vector identic cu cel de puncte numai ca fac swap(aux[0],aux) pentru a putea sorta apoi...

Cod:

		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				aux[j]=a[j];
			swap(aux[0],aux[i]);
			sort(aux+1,aux+n+1,cmp);//cu stable_sort intra-n timp
                        .... mai jos fiind parcurgerea liniara

Am incercat si cu memcpy si degeaba
Iar la comparare fac produsul mezilor cu extremii ca sa nu pierd precizie...

Cod:

inline ll calc(p x,p y)
{
	return (ll)(x.second-aux[0].second)*(y.first-aux[0].first);
}
inline int cmp(p x, p y)
{
	return calc(x,y)<calc(y,x);
}

L.E. Dupa mai multe modificari dar nu prea esentiale am descoperit greseala ) Citeam n si daca era 1 sau 2 afisam 1 respectiv 2 si treceam la testul urmator fara sa mai citesc elementele (1 respectiv 2) 

[•alexandru92]

Imi poateti spune ce este gresit la urmatoarea sursa  . Am dat zeci si zeci de teste si imi afiseaza corect ( am verificat cu o sursa destul de simplu de scris  folosind un map< double, int > )

Cod:

inline ll get( pr p1, pr p2 ) //pr pair< int, int >
{
    return (ll) ( (ll)(p1.first-p0.first)*(ll)(p2.second-p0.second) );
}
inline bool cmp( pr p1, pr p2 )
{
    return get( p1, p2 ) < get( p2, p1 );
}
inline int max( int x, int y )
{
    return x^( (x^y) & -(x<y) );
}
int main()
{pr v[Nmax], v2[Nmax];
int n, t, i, j, k, maxim, length;
    freopen("flori2.in", "rt", stdin );
    freopen("flori2.out", "wt", stdout );
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d", &n );
        for( i=0; i < n; ++i )
            scanf("%d%d", &v[i].first, &v[i].second );
        maxim=0;
        for( i=0; i < n; ++i )
        {p0=v[i]; length=0;
            for( j=0; j < n; ++j )
                if( i != j )
                    v2[length]=v[j], ++length;
            stable_sort( v2, v2+length, cmp );
            for( j=0; j < length; j=k )
            {
                for( k=j+1; k < length && get( v2[k], v2[j]) == get( v2[j], v2[k] ); ++k );
                maxim=max( maxim, k-j );
            }
        }
        printf("%d\n", maxim+1 );
    }
    return 0;
}

[•ciprianf]

Nu uitati cazul cand N = 1

[•geniucos]

Imi poate spune si mie cineva ce am gresit,am facut cu ideea lui Dragos Oprica si testele pe care le-am dat mi-au mers.

Cod:

scanf("%d",&n);
for(i=1;i<=n;i++)
{
	scanf("%d",&x[i]);
	scanf("%d",&y[i]);
}
maxi1=0;
for(i=1;i<=n;i++)
{
	for(j=1;j<=n;j++)
		if(i!=j)
		{
			if(x[j]!=x[i]) m[j]=(double)(y[j]-y[i])/(x[j]-x[i]);
			else m[j]=-10000002;
		}
	m[i]=-10000004;
	sort(m+1,m+n+1);
	nr=1;
	maxi=0;
	for(j=2;j<=n;j++)
	{
		if(abs(m[j]-m[j-1])<=0.0000001) nr++;
		else
		{
			if(nr>maxi) maxi=nr;
			nr=1;
		}
	}
	if(nr>maxi) maxi=nr;
	if(maxi>maxi1) maxi1=maxi;
}
printf("%d\n",maxi1+1);

Editat de admin: foloseste tagul "code" cand postezi surse.

[•ionut98]

Cam ce complexitate ar trebui sa am?

Eu am O(T*N*N*logN)

[•klamathix]

Ar trebui să fie ok complexitatea asta, tu probabil iei TLE fiindcă apelezi de prea multe ori atan2(), care e cam înceată. Încearcă să precalculezi o singură dată atan2()-urile într-un array, iar apoi să folosești acest array pentru sortare și pentru comparațiile ulterioare.

Poți să ajungi și la $O(T * N * N)$ dacă pui pantele în ceva hash-like ca să le contorizezi frecvențele (spre exemplu un unordered_map). Eu aș încerca ambele variante.