497 Mosia

[•DITzoneC]

Aici puteţi discuta despre problema Mosia.

[•anna_bozianu]

"Pe urmatoarele N+1 linii, se afla cate 3 numere x, y, d, reprezentand...."
 
Intrebare :
Pana la urma avem N laturi sau N+1?

"In fisierul mosia.out se scrie un numar real cu cel putin 4 zecimale ce reprezinta suprafata maxima cu care se poate mari mosia."

Intrebare :
Ce inseamna cu cel putin 4 zecimale? Pun aceasta intrebare pentru ca eu pierd ultimele teste in care probabil N este mai mare. Banuiesc ca nu algoritmul meu este de vina ci precizia cu care afisez rezultatul. Poate cineva sa imi sugereze unde s-ar putea crea erori de calcul? Mentionez ca am incercat sa fac imlementare si cu double si cu long double iar afisarea am facut-o cu "%.4lf" respectiv "%.4Lf" si "%.10Lf". In toate aceste cazuri pierd toate testele incepand cu testul 12 si exeptand testul 15 obtinand astfel 60p. Nu fac nicio aproximare pe parcurs. Oare ce gresesc?

[•devilkind]

afisarea la long double e cu %.4llf

[•anna_bozianu]

" The L modifier may also prefix the floating-point specifiers e,f and g and indicates a long double follows."
                Herb Schildt- C The complete reference-second edition



Oricum nu asta cred ca e problema.  Eu adun acolo niste valori pentru anumiti pari pe care ii mut. Problema e ( cred eu) ca la mai multe valori adunate se aduna "resturi" care imi modifica ultima dintre cele 4 zecimale afisate. Posibil sa am erori la calculul ariei castigate la fiecare mutare. 

[•pauldb]

"Pe urmatoarele N+1 linii, se afla cate 3 numere x, y, d, reprezentand...."

Intrebare :
Pana la urma avem N laturi sau N+1?

Am modificat.

"In fisierul mosia.out se scrie un numar real cu cel putin 4 zecimale ce reprezinta suprafata maxima cu care se poate mari mosia."

Intrebare :
Ce inseamna cu cel putin 4 zecimale? Pun aceasta intrebare pentru ca eu pierd ultimele teste in care probabil N este mai mare. Banuiesc ca nu algoritmul meu este de vina ci precizia cu care afisez rezultatul. Poate cineva sa imi sugereze unde s-ar putea crea erori de calcul? Mentionez ca am incercat sa fac imlementare si cu double si cu long double iar afisarea am facut-o cu "%.4lf" respectiv "%.4Lf" si "%.10Lf". In toate aceste cazuri pierd toate testele incepand cu testul 12 si exeptand testul 15 obtinand astfel 60p. Nu fac nicio aproximare pe parcurs. Oare ce gresesc?

Eu am afisat printf("%lf\n",sol);

[•anna_bozianu]

Multe multumiri. Am reusit. Se pare ca totusi greseam si la asezarea punctelor in sens trigonometric la configuratia initiala. 

[•zbarni]

Testele sunt cele de la oji? Pe testele de acolo imi da 100 de puncte, iar aici nu iau decat 15 Afisarea fac cu streamuri, deci problema sigur nu e de acolo. Any help?
Ar fi binevenit si testul 3, sau 4 de exemplu. Ms.

[•pauldb]

Din cate tin minte, testele de la OJI se afla printre testele oficiale, dar mai sunt si altele.

[•zbarni]

Atunci nu stiu ce este, pe testele alea imi da bine, si totusi iau 15 puncte  Am incercat sa afisez si cu 4,5,si 6 zecimale..

[•johsonsbabi]

nu inteleg explicatia?

stalpul 3 si 4 nu se muta?

[•chera_lary]

Salut!
Care este dinamica de la problema aceasta?

[•DraStiK]

Salut!
Care este dinamica de la problema aceasta?

Dinamica "o citești" din enunț:

best[ i ] = aria maxima care se poate obține efectuînd operații pe primii i pari; trebuie sa ai grija ca parii sunt circulari

[•chera_lary]

Asta-i tot ceea ce am reusit sa implementez, dar nu obtin decat 40 de p. 
Sortarea este cea de la infasuratoarea convexa. Scanarea Graham.

Cod:

s1[1] = c[1]; //s1[i] = suma maxima editandu-se primii i pari, c[i] = aria pe care o castiga prin mutarea parului i
	sm1[1] = 1; // sm1[i] = retine 1 daca s-a mutat parul i, 0 in caz contrar
	if(c[1] > c[2]) s1[2] = c[1], sm1[2] = 0; else s1[2] = c[2], sm1[2] = 1;
	for(int i=3;i<n;i++)
	{
		if(s1[i-2] + c[i] > s1[i-1]) s1[i] = s1[i-2] + c[i], sm1[i] = 1; else s1[i] = s1[i-1], sm1[i] = 0;
	}
	
	s2[2] = c[2];
	sm2[2] = 1;
	if(c[2] > c[3]) s2[3] = c[2], sm2[3] = 0; else s2[3] = c[3], sm2[3] = 1;
	for(int i=4;i<=n;i++)
	{
		if(s2[i-2] + c[i] > s2[i-1]) s2[i] = s2[i-2] + c[i], sm2[i] = 1; else s2[i] = s2[i-1], sm2[i] = 0;
	}
	
	smax1 = s1[n-1]; smax2 = s2[n];
	if(!(sm1[1]) && !(sm1[n-1])) smax1 += c[n];
	if(!(sm2[2]) && !(sm2[n])) smax2 += c[1];

           float smax = max(smax1, smax2);

Cod:

inline bool cmp(int a, int b)
{
	return (float)(x[a] - x[PI])*(y[b] - y[PI]) < (float)(x[b] - x[PI])*(y[a] - y[PI]);
}

for(int i=1;i<=n;i++)
	{
		if(i == PI) continue;
		IN[++IN[0]] = i;
	}
	
	sort(IN + 1, IN + IN[0] + 1, cmp);
	IN[++IN[0]] = PI;
	
	for(int i=1;i<=n;i++)
	{
		int dr = i+1, st = i-1;
		if(dr > n) dr = 1;
		if(st < 1) st = n;
		float D = (float)dist((float)x[IN[st]], (float)y[IN[st]], (float)x[IN[dr]], (float)y[IN[dr]]);
		c[i] = (float)(D * d[IN[i]]) / 2;
	}

[•DraStiK]

Nu am stat sa verific dacă faci corect ceea ce faci, pentru ca mie nu mia ieșit sortarea cu cea de la înfășurătoare convexa. Eu am folosit ca funcție de comparare aici atan2 - care e defapt tangata unghiului.

uite cum e funcția mea de comparare pentru sort:

Cod:

int cmp (punct a,punct b)
{
    return atan2 (a.y-gy,a.x-gx)<atan2 (b.y-gy,b.x-gx);
}

și g - centru de greutate al poligonului

[•APOCALYPTO]

Salut!
Nici mie nu imi merge programul daca folosesc sortarea de la Algoritmul lui Graham.
Cum pot afla centrul de greutate inainte sa stiu infasuratoarea convexa?

[•cosmin79]

Centrul de greutate are ca, coordonate x=media aritmetica a x-ilor si y=media aritmetica a y-ilor

[•APOCALYPTO]

Imi cer scuze.
Cred ca nu m-am facut inteles.
Ma intereseaza daca acele 2 medii(media X-ilor si media Y-ilor) le calculez pentru toate punctele din input sa numai pentru cele din infasuratoarea convexa?

In mod normal as crede  ca trebuie facuta media numai pentru coordonatele de pe infasuratoarea convexa, dar nu o cunosc dinainte.

[•pauldb]

Centrul de greutate are ca, coordonate x=media aritmetica a x-ilor si y=media aritmetica a y-ilor

Facand media coordonatelor nu se obtine centrul de greutate. O formula pentru a-l obtine se gaseste aici (in engleza se numeste centroid).

@Dragos: De ce ai nevoie de centrul de greutate?

[•APOCALYPTO]

Centrul de greutate are ca, coordonate x=media aritmetica a x-ilor si y=media aritmetica a y-ilor

Facand media coordonatelor nu se obtine centrul de greutate. O formula pentru a-l obtine se gaseste aici (in engleza se numeste centroid).

@Dragos: De ce ai nevoie de centrul de greutate?

Am nevoie de centrul de greutate pentru ca Drastik a zis ca l-a folosit la sortarea punctelor.
Daca folosesc sortarea de la scanarea Graham( cea cu aleg punctul cel mai din stanga, iar in caz de egalitate pe cel mai de jos si sortez dupa unghi) nu merge.
 De exemplu pentru testul:

Cod:

8
0 0 2
2 0 3
0 1 2
0 -1 1
1 1 2
2 -1 4
2 1 3

Punctul A e cel mai din stanga si cel mai de jos. Dupa cum se poate vedea unnghiul facut cu B este egal cu unghiul facut cu C si unghiul facut cu H este egal cu cel facut cu G.
Dar ordine in care trebuie sa le am dupa sortare este A B C D E F G H fiindca am nevoie de toate punctele de pe infasuratoarea convexa.
Daca sortez numai dupa unghiul facut cu A este foarte probabil ca C sa fie inainte de B si H inante de G si cand voi aplica cealalta parte a algoritmului Graham punctele C si H  vor fi pierdute.

[•vladii]

Am rezolvat problema asta acum mult timp, dar m-am uitat in sursa si eu am luat 100 cu urmatoarea sortare:

Cod:

int Produs(Puncte P1, Puncte P2, Puncte P3) {
    return P2.x*P3.y - P2.x*P1.y - P1.x*P3.y + P1.x*P1.y - 
           P3.x*P2.y + P3.x*P1.y + P1.x*P2.y - P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
    if((a.x-P[1].x)*(b.y-P[1].y)!=(b.x-P[1].x)*(a.y-P[1].y)) {
         return (a.x-P[1].x)*(b.y-P[1].y) > (b.x-P[1].x)*(a.y-P[1].y);
    }
    else if(P[1].y==a.y && P[1].y==b.y) {
         return (a.x-P[1].x)*(a.x-P[1].x) + (a.y-P[1].y)*(a.y-P[1].y) <
                (b.x-P[1].x)*(b.x-P[1].x) + (b.y-P[1].y)*(b.y-P[1].y);
    }
    else if(!Produs(a, b, P[1])) {
          return a.x<b.x;
    }
}

P[1] este punctul din stinga jos.

Poate te ajuta cu ceva. Bafta !

[•APOCALYPTO]

Am rezolvat problema asta acum mult timp, dar m-am uitat in sursa si eu am luat 100 cu urmatoarea sortare:

Cod:

int Produs(Puncte P1, Puncte P2, Puncte P3) {
    return P2.x*P3.y - P2.x*P1.y - P1.x*P3.y + P1.x*P1.y - 
           P3.x*P2.y + P3.x*P1.y + P1.x*P2.y - P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
    if((a.x-P[1].x)*(b.y-P[1].y)!=(b.x-P[1].x)*(a.y-P[1].y)) {
         return (a.x-P[1].x)*(b.y-P[1].y) > (b.x-P[1].x)*(a.y-P[1].y);
    }
    else if(P[1].y==a.y && P[1].y==b.y) {
         return (a.x-P[1].x)*(a.x-P[1].x) + (a.y-P[1].y)*(a.y-P[1].y) <
                (b.x-P[1].x)*(b.x-P[1].x) + (b.y-P[1].y)*(b.y-P[1].y);
    }
    else if(!Produs(a, b, P[1])) {
          return a.x<b.x;
    }
}

P[1] este punctul din stinga jos.

Poate te ajuta cu ceva. Bafta !

M-a ajutat!
Multumesc!!! 

[•Theory]

Poate sa imi spuna cineva cat da pentru urmatorul test?

Cod:

19
-6 19 1
18 -17 9
-16 -18 8
-19 -3 10
19 -8 10
17 18 3
19 -12 2
-8 -19 3
-19 16 7
-18 -16 7
19 -6 9
-17 18 5
19 15 2
-19 -2 3
13 19 4
7 -19 10
0 19 6
-19 -15 5
-4 -19 1

[•PlayLikeNeverB4]

Cod:

467.9360045

[•japjappedulap]

Se pot muta pari consecutivi?

[•margiki]

Pentru cei care iau 60p:

Faceti infasuratoarea in jurul celui mai de jos - stanga punct, si nu stanga - jos.