112 Arie

[•domino]

Aici puteţi discuta despre problema Arie.

[•spatarel]

Problema asta mi se pare cea mai grea de pe siteul asta

In special testul 1!

Poate cineva sa-mi dea macar un hint, cu ce este?

Eu am incercat foarte multe teste si toate au fost ok! Am incercat si tot felul de cazuri particulare (poligon in poligon, poligoanele au o latura comuna, poligoanele sunt identice, poligoanele au un pct. comun - oare ce n-am incercat???) si nimic...

Trebuie sa afisez ceva deosebit, intr-un anumit caz? (ex.: 0, in loc de 0.000, atunci cand poligoanele nu se intersecteaza?)

[•Cosmin]

Mie mi se pare destul de simpla, am facut-o in vreo jumatate de ora sau mai putin si a mers din prima, eu mergeam din aproape in aproape cu o linie de baleiere si verificam intersectiile cu poligoanele, ariei ii adaugam eps * (x3-x2).

[•spatarel]

Tx. for the advice

Eu am incercat s-o fac clasic, ca pentru limite mai mari

Mai exact:
1) pun intr-o lista punctele care:
- definesc un poligon si sunt in interiorul celuilalt;
- rezulta din intersectia a doua laturi, apartinand una unui poligon si cealalta celuilalt
2) pentru punctele din lista, aplic infasuratoare convexa
3) Calculez aria poligonului rezultat

Teoretic ar trebui sa mearga pe orice test . Ma gandesc ca poate am gresit un detaliu stupid... si eram curis ce (din greseli se invata ).

Cred ca o sa fac si eu cu baleiere... damn...

Si totusi... daca faci cu baleiere, nu e posibil sa pierzi precizie? (Ma gandesc asa: daca micsorezi eps-ul, creste precizia, dar scade timpul de executie, si invers...)

[•bogdan2412]

Rezolvarea cu infasuratoarea convexa este buna si merge pentru toate cazurile. Ai o greseala in implementare undeva...

[•spatarel]

M-am prins si eu ca am o greseala pe undeva.
Din cauza asta ceream un hint legat de structura primului test.

[•spatarel]

Foarte grea problema asta!

Pt. cei care au probleme cu testul 1 - solutia este "0.000" si eu afisam "0.001"  

Spor!

[•Coty]

punctele... sunt direct varfurile poligonului sau trebuie sa mai facem noi inchiderea convexa a lor?

[•filipb]

Sunt direct varfurile poligonului.

[Tabara Mihai]

azi se implinesc 60 de zile de cand ma chinui la problema asta.....hm... nu e neaparat foarte grea insa este minutioasa...x puncte de intersectie dupa care un Graham pentru ele si apoi calcul de arie cu determinant.....nu stiu de ce nu-mi iese? ....cred ca am o greseala  la aflarea punctelor de intersetie.....la naiba!

[•MarcvsHdr]

Nu inteleg de sa mai faci infasuratoarea convexa la punctele de intersectie. Ele deja sunt pe o infasuratoare convexa, nu? In fond intersectia a doua poligoane convexe e un poligon convex, deci nu poate avea varfuri pe undeva prin interior.
Trebuia doar sa le sortezi trigonometric in jurul unuia dintre ele (am ales cel mai din stga si la egalitate, cel mai de jos).
Chestia e ca primesc WA pe 3 teste.... (nu, nu e vorba de testul 1, ci de testele 3, 8 si 9). Sunt foarte naspa problemele astea de geometrie analitica, implementez la ea de vreo 5 ore, am subit-at-o de 3 ori si ceva tot e gresit.
Macar de as avea un test pe care nu merge .
Eu am pus intr-o lista:
1. toate punctele de intersectie dintre laturile poligoanelor
2. toate varfurile din P1 care sunt in interiorul SAU pe perimetrul lui P2
3. toate varfurile din P2 care sunt in interiorul SAU pe perimetrul lui P1
testez daca un punct e intr-un poligon sau pe perimetrul lui daca suma ariilor triunghiurilor de la el la laturi e egala cu aria poligonului.

Sortez si calculez aria cu determinant.

Oricum, ma mai gandesc, ceva TREBUIE sa imi scape din vedere.

(later edit)
Mda, dupa 5 ore pierdute cu problema asta, am realizat ca sortam gresit punctele cu panta=infinit (de jos in sus in loc de sus->jos). Eh, se mai intampla, sa nu patiti si voi

[•cretu]

ati putea va rog sa postati testele 1 si 3 pe forum? vreau sa ma conving daca rationamentul meu e bun (si am doar erori de precizie pe 3 teste) sau nu.

[•wefgef]

Din pacate la problemele din arhiva testele nu se fac publice.

[•cretu]

ok nu-i bai. Mi-am dat seama ce greseam numai k tot imi pica pe testul 3. E evil

[•taloibogdan]

Nu inteleg!!!
Am facut cu baleere.
Cand am precizia 0.001 imi merge testul 7.
Cand 'maresc' precizia la 0.0005 nu imi mai merge testul 7.(cu toate ca 0.0005 divide 0.001)
Si daca cumva am precizia prea 'mare'... de ce cand o fac 0.0001 imi merge testul 7(pacat ca nu imi intra in timp 4 teste) ? ? ?

[•pauldb]

O precizie cat mai mica nu te avantajeaza de fiecare data. Din cauza operatiilor pe numere reale, rezultatele sunt rotunjite si uneori diferenta dintre rezultatul asteptat si cel obtinut este considerabila.

Sfatul meu e sa incerci sa folosesti cat mai putine operatii pe numere reale inainte de a micsora precizia.

[•Addy.]

Ma poate ajuta cineva la problema asta? Cred ca este din cauza preciziei cu numere reale... Dupa ce am folosit o functie de 'egal' am sarit de la 0 la 60 de puncte. Vad ca au mai fost si alte persoane cu probleme pe testele respective.

Cod:

bool egal (double a, double b) {
	
	double c = a - b;
	if (c < 0) c = -c;
	
	if (c < 0.00000000001) return 1;
	return 0;
}

[•ctlin04]

Stie cineva ce are testul 3, ca nu ma pot prinde nicidecum 

[•Impaler_009]

Pentru toti cei care se zbat cu problema asta: Trebuie sa afisezi EXACT 3 zecimale, nici mai mult, nici mai putin. Deci, fout<<fixed<<setprecision(3)<<A; neaparat.