BitCell

Deci, cunoastem coordonatele varfurilor unui triunghi intr-un sistem ortogonal de axe xOy :
Cum aflam aria ?
Am gasit o formula ,cum ca:

Nu exista alta modalitate ? Am intampinat la o problema si inca nu am facut despre matrici d-astea.. Multumesc!

Folosește despachetarea Laplasiană. Este și un exemplu pe wiki despre cum ai putea face asta.

Hai hai,
Spor!

Dar asta e formula cea mai simpla dupa parerea mea, calculezi determinantul matricei respective si il inmultesti cu 1/2 .

Hmm, mi-ar fi greu,n-am facut nimic despre matrici la scoala ,inca.. si nici timp mult la dispozitie n-am sa incerc io sa le inteleg..
Oricum,ar fi o alta solutie pentru problema de mai jos care nu s-ar baza pe metoda asta de aflare a ariei ?
Cum imi propusesem sa fac..
Pentru cerinta de la punctul A) Pentru a verifica dacă F( fantana,de coordonate x,y ) este in interior sau pe frontiera unui triunghi este suficient să verificăm dacă:
Pentru cerinta de la punctul B) trebuie doar sa aflam triunghiul cu arie maxima..

În comuna Triunghi din România sunt n ţărani codificaţi prin numerele 1, 2, ..., n. După anul 1990 a început retrocedarea suprafeţelor de pământ deţinute înainte de colectivizare. Fiecare ţăran are un document prin care dovedeşte că este proprietar pe o singură suprafaţă de teren de formă triunghiulară. Din păcate, documentele dau bătaie de cap primarului (care se ocupă de retrocedarea suprafeţelor de pământ), pentru că sunt porţiuni din suprafeţele de pământ care se regăsesc pe mai multe documente.
În această comună există o fântână cu apă, fiind posibil ca ea să fie revendicată de mai mulţi ţărani. O suprafaţă de pământ este dată prin coordonatele celor trei colţuri, iar fântâna este considerată punctiformă şi dată prin coordonatele punctului.

Cred ca mai bine ar trebui sa astept pana vom face despre matrici la scoala, nu ?:)))
 
Cerinţă
Să se scrie un program care să determine:
a) Codurile ţăranilor care au documente cu suprafeţe de pământ ce conţin în interior sau pe frontieră fântâna.
b) Codul ţăranului ce deţine un document cu suprafaţa de teren, care include toate celelalte suprafeţe.
 
Date de intrare
Fişierul de intrare triunghi.in are pe prima linie numărul n de ţărani, pe următoarele n linii câte 6 valori numere întregi separate prin câte un spaţiu, în formatul: x1 y1 x2 y2 x3 y3, ce reprezintă coordonatele celor trei colţuri ale suprafeţei triunghiulare deţinute de un ţăran. (x1, x2, x3 abscise, iar y1, y2, y3 ordonate). Pe linia i+1 se află coordonatele colţurilor suprafeţei de teren triunghiulare deţinute de ţăranul i, i=1,2,…,n. Ultima linie a fişierului (linia n+2) va conţine coordonatele fântânii în formatul x y, cu un spaţiu între ele (x abscisă, iar y ordonată).
 
Date de ieşire
Fişierul de ieşire triunghi.out va conţine pe prima linie răspunsul de la punctul a), adică: numărul de ţărani care îndeplinesc condiţia din cerinţă şi apoi codurile lor (în ordine crescătoare), cu un spaţiu între ele. Dacă nu există ţărani cu condiţia din cerinţă, pe prima linie se va scrie cifra 0. Pe linia a doua se va scrie răspunsul de la punctul b), adică: codul ţăranului cu proprietatea cerută, sau cifra 0, dacă nu există un astfel de ţăran.
 
Restricţii
• 2 ≤ n ≤ 65
• coordonatele colţurilor suprafeţelor de pământ şi ale fântânii sunt numere întregi din intervalul [-3000, 3000]
• cele trei colţuri ale fiecărei suprafeţe de pământ sunt distincte şi necoliniare
• nu există doi ţărani care să deţină aceeaşi suprafaţă de pământ
• nu se acordă punctaje parţiale.
 
 
Exemple    
 triunghi.in                         

 
triunghi.out

 
    La punctul a), sunt doi ţărani care deţin suprafeţe de pământ ce au în interior sau pe frontieră fântâna, cu codurile 1 şi 2.
La punctul b), ţăranul cu codul 2 deţine o suprafaţă de teren care include, suprafeţele de pământ deţinute de ceilalţi ţărani (cu codurile 1 şi 3).

Sau mai bine astept pana facem matrici la scoala,nu ? Daca as sti sa fac aria aia..problema e mai multa geometrie,sau..se poate rezolva si fara ? Un algoritm, ceva..

Ar mai fi o modalitate simpla (de gandit) . Afli laturile triunghiului cu formula matematica (de la vectori) pentru ca ai coordonatele, si apoi folosesti formula lui Heron pentru arie. Asta cel putin as face eu daca as intalni o problema asemanatoare. Modalitatea nu este complicata (cu privire la rationament) dar este cam greu de "pus in practica" si este si foarte lenta, dar conteaza ca rezolva intr-un final problema.

Cosmin_NTG wrote:Ar mai fi o modalitate simpla (de gandit) . Afli laturile triunghiului cu formula matematica (de la vectori) pentru ca ai coordonatele, si apoi folosesti formula lui Heron pentru arie. Asta cel putin as face eu daca as intalni o problema asemanatoare. Modalitatea nu este complicata (cu privire la rationament) dar este cam greu de "pus in practica" si este si foarte lenta, dar conteaza ca rezolva intr-un final problema.

Pot sa spun ca mi-a trecut si mie prin minte... Dar cum afli laturile triunghiului ca sa afli semiperimetrul?

E mult mai simplă problema decât pare:

În primul rând, ideea ta de rezolvare de la punctul B nu este bună. Dacă triunghiul are arie imensă , dar se află la cuca măcăii și nu include nici un alt triunghi, iar un alt triunghi al unui oarecare vasile are arie mai mică, dar totuși le include pe celealte, ce faci?

Pentru punctul A îți dau un HINT:
Dacă ai învățat despre drepte, ecuația dreptei și despre pante e destul de simplu. Îți spun sigur că există o modelitate simplă de a-ți da seama DACĂ un punct se află de o parte sau de alta a dreptei (sau pe dreaptă). Astfel, poți afla dacă un punct (fântâna) este în interior unui triunghi (chiar și pe muchie).

Fă niște teste:
Ai o ecuație a unei drepte ax+by+c = 0 (alegi la întâmplare ceva rezonabil - te poți verifica cu wolframalpha).
Înlocuiește pe x și y din ecuație cu coordonatele mai multor puncte aleatorii - câteva de o parte a dreptei, câteva de cealaltă parte a dreptei. Dacă înlocuiești pe x și y cu un punct de coordonate care se află pe dreaptă, rezultatul va fi 0 (evident - așa verifici dacă un punct se află sau nu pe dreaptă). Dar noi urmărim ce se întâmplă și dacă punctul se află lângă dreaptă.
Verifică rezultatele și vezi ce observi! Apoi, încearcă pe un triunghi, află cele 3 ecuații ale dreptelor și află o regulă după care să-ți dai seama dacă un punct se află sau nu în interiorul unui triunghi.

Ce pot sa zic..
Pentru punctul B..Mi-a scapat .. pentru acest triunghi cu arie maxima verificam dacă toate celelalte n-1 triunghiuri sunt interioare sau pe frontiera (adică dacă au toate vârfurile în interiorul sau pe frontiera acestui triunghi cu arie maxima).
Pentru punctul A , ma mai gandesc imediat ce termin de lucru ceva mai urgent..

Și dacă nu îs interioare triunghiului cu arie maximă, ce faci? Iei următorul triunghi cu arie maximă (mai mică totuși decât cel inițial)? Ineficient. Fă punctul A iar B va fi foarte simplu după ce te prinzi la A.

LE: Am greșit. Dacă există un triunghi care într-adevăr le cuprinde pe toate, va avea arie maximă. Dar nu și invers! Totuși, nu se menționează (cel puțin nu am citit eu) să zică ce se întâmplă dacă nu există un triunghi care să le cuprindă pe toate?\

LE2: Mda, se afișază 0 dacă nu exstă un astfel de țăran (triunghi). Well, tot e bine în mare parte ce am spus. Totuși, am fost neatent că-s pe fugă. Acuma îl înțeleg parcă pe moderatorul nostru Mihai...
Deci e bun raționamentul cu aria maximă && dacă sunt toate punctele în interior => există țăran care să îi cuprindă pe toți. Altfel, nu.

noobakaflo wrote:

Cosmin_NTG wrote:Ar mai fi o modalitate simpla (de gandit) . Afli laturile triunghiului cu formula matematica (de la vectori) pentru ca ai coordonatele, si apoi folosesti formula lui Heron pentru arie. Asta cel putin as face eu daca as intalni o problema asemanatoare. Modalitatea nu este complicata (cu privire la rationament) dar este cam greu de "pus in practica" si este si foarte lenta, dar conteaza ca rezolva intr-un final problema.

Pot sa spun ca mi-a trecut si mie prin minte... Dar cum afli laturile triunghiului ca sa afli semiperimetrul?

Pai asta cu aflatul laturilor am spus, dar nu am fost indeajuns de explicit.
Deci la matematica (la vectori mai exact) am invatat (eu cel putin) o formula care calculeaza distanta dintre doua puncte atunci cand se stiu coordonatele lor:


Sper ca am fost indeajuns de explicit acum.

A mutat topicul la secțiunea de algoritmică deoarece nu cred că contează limbajul în care faci problema. Până la urmă, presupun că e ceva pregătire pentru olimpiada de info - care ține în cea mai mare parte de algoritmică și nu de un limbaj anume.

Cam greu de inteles, eu dau doua metode:
1. Flosesti formula lui heron , pentru a afla lungimea laturilor folosesti formula:

Exemplu pentru latura 1-2: D1-2=sqrt(((x2-x1)^2-(y2-y1)^2). Folosesti formula pentru cele trei laturi si apoi restul e mai usor de calculat.

2. Doua formule care se folosesc in topografie:*

Detalii legate de formula Xi(Yi+1 - Yi-1) cu exemplu:
Se ia primul punct pentru care folosim:
S=1/2 * (X1(Y2-Y3)+X2(Y3-Y1)+X3(Y1-Y2))
*Se foloseste doar una din formule.

Am gasit in alta parte cum aria cu determinanti ar fi egala cu ..

Incerc sa o folosesc pe asta..
Am incercat si cu aria lui Heron , dar mi s-a parut greoaie de implementat ..Poate si mai ineficienta , 'sqrt' folosit de mai multe ori...

^Păi așa se calculează determinații de ordin 3.
http://www.e-formule.ro/wp-content/uploads/determinantul-matricei.htm
Acolo sunt niște imagini cu linii colorate care îți arată cum trebuie să înmulțești elementele pentru a calcula determinantul...

Dar eu nu înțeleg de ce nu te ocupi de punctul A.