011 Copaci

[•fluffy]

Aici puteţi discuta despre problema Copaci.

[TheWoolf]

cum da mah 21 exemplu??
mie imi da 14 asa facut de mana...nush...nu ma prind...

[•LordAnta]

Fa de mana si ai sa vezi !!! =;

[TheWoolf]

pai am facut de mana si nam vazut..

[•rss1987]

sigur ai folosit foaie de matematica?..si vezi sa nu le numeri pe alea care sunt pe granita..foloseste si o rigla ca sa-ti iasa bine poligonu'.

[TheWoolf]

Ooops ..my bad..
am desenat eu gresit...gata am luat 100...np..merge..e bine..

[•stifmeister]

Cine imi spune mie cum merge exact algoritmul care verifica daca un punct apartine interiorului unui poligon oarecare?
    Daca numar toate punctele de intersectie de la dreapta punctului cu laturile poligonului imi da, dar ce se intampla daca dreapta intersecteaza un varf al poligonului?


    Si sa imi spuneti si mie daca acest algoritm s-ar putea adapta pentru aceasta problema. (Din punct de vedere al timpului de executie, pentru ca banuiesc ca altfel nu ar fi probleme).


Multumesc mult!!!

[•rss1987]

In primul rand varianta asta nu te ajuta la rezolvarea problemei.
Dar pentru stiinta iti explic:

cand intalnesti un punct de pe poligon te uiti la cele doua segmente care il contin: daca ambele seg au celalalt capat de aceeasi parte a dreptei ignori intersectia, altfel o numeri. Mai exista cazul cand intalnesti segmente ale poligonului care sunt incluse in dreapta de scanare. Le ignori pur si simplu de parca nici n-ar exista. Ok?

Ar trebui sa-ti dea raspunsul corect...  

[•rss1987]

Testu' 2 e cu shmen? tot iau WA...daca se poate va rog sa mi-l postati...

[•stifmeister]

Ce complexitate are solutia comisiei?

Imi da cineva si mie o indicatie?

[•cavendish]

probabil O(N) cu o ct destul de mica.

E o relatie matematica data de Teorema unui tip smecher   . Nu-ti zic cum il cheama ca atunci ar fi prea evident... . Mai cauta relatii in triunghiul oarecare...

[cristi8]

probabil O(N) cu o ct destul de mica.

E o relatie matematica data de Teorema unui tip smecher   . Nu-ti zic cum il cheama ca atunci ar fi prea evident... . Mai cauta relatii in triunghiul oarecare...

dc in triunghi oarecare ? ..nu merge cu "P***'s Theorem" ?

[•Cosmin]

cmmdc are complexitate logaritmica deci solutia nu e chiar O(n)

[•stifmeister]

Am cautat dar nu am auzit sa fi cercetat Pitagora sau altcineva cati copaci intra intr-un triunghi oarecare.
Am descoperit totusi ceva intre cmmdc si triunghiul dreptunghic ( atatea indicii am primit).
Si anume: numarul punctelor de coordonate intregi din interiorul unui triunghi cu varfurile de asemenea de coordonate intregi este:
[ (a-i)(b-1) - cmmdc(a, b) + 1]/2. Mi se pare chiar foarte corecta formula si nu cred ca e greu de gasit. Adica intru-un dreptunghi sunt (a - 1)(b - 1) puncte de coordonate intregi iar intr-un triunghi dreptunghic sunt  cam jumatate ( pentru ca scadem  numarul de puncte de pe diagonala dreptunghiului care au coordonate intregi).
Nu?
Se poate generaliza si la un triunghi oarecare daca este nevoie ( il incadrez intr-un dreptungi si scad punctele din cele 3 triunghiuri dreptunghice care apar).
Asa... si daca asta este formula pe care mi-ai cerut-o, atunci ce fac mai departe?

[•Cosmin]

Ii zice teorema lui Pick, daca vrei sa citesti mai mult pe tema asta poti sa te uiti aici: http://www.geometer.org/mathcircles/pick.pdf . Mai trebuie sa ai grija la punctele de coordonate intregi care sunt pe laturile poligonului.

[TheWoolf]

Ai stricat toata distractia...Booo!!!

[•Cosmin]

Ce distractie? E problema daca stii sau nu teorema, oricum e de antrenament, cu ce esti mai tare ca ai auzit de teorema dinainte sau nu ...

[•bogdan2412]

Ok am calculat aria poligonului si numarul de puncte de coordonare intregi de pe laturi si apoi am folosit teorema lui Pick ca sa aflu numarul de puncte din interiorul poligonului. Aria am calculato cu formula cu determinanti si pentru numarul de puncte de pe laturi am folosit urm metoda: initial variabila B e 0 si luam laturile pe rand (inclusiv latura dintre punctul n si punctul 1) adunand de fiecare data cmmdc(|x-x[i-1]|,|y-y[i-1]|)... Mie mi se pare corecta rezolvarea dar totusi am primit WA la testu 5-10. Poate cineva sa ma ajute?

[•gogu]

Testele 5-10 poti sa le iei daca faci doar aria poligonului, puncte fiind pe laturi parca doar la testele 1-4, cele care le iei(asa a fost la mine, dupa ce am ignorat varfurile aflate intre alte 2 varfuri).
Poate nu iei varfurile ca puncte de pe laturi, nu stiu ce sa zic.
Oricum, ti-au iesit testele mai grele, vezi ca poate nu iti merge cmmdc in unele cazuri, nu stiu.

[•bogdan2412]

Tu cum ai calculat aria poligonului? Am incercat de test sa scot cautarea punctelor pe laturi si am luat 0 puncte sa vad daca aici era problema, deci am gresit ceva la calcularea ariei...

[•gogu]

Aria am facut-o cu determinanti. Imparteam poligonul in n-1 triunghiuri cu varfuri in punctele p0 pi si pi+1. Tu cum faci?

[•bogdan2412]

Da aveam o greseala la calcularea ariei... Bine, eu inca nu m-am prins ce gresisem, dar pur si simplu am luat programul principal, am apasat delete si l-am scris din nou. Multumesc pentru ajutor

[•sarabogdan]

Aria o fac asa

Cod:

a[n+1] = a[1];

for (i =1 ; i<= n ; i++) 
     aria+= a[i].x*a[i+1].y-a[i].y*a[i+1].x;

Pentru numarul punctelor de pe o latura fac
cmmdc(|a.x - a[i+1].x|,|a.y - a[i+1].y|)

Ce gresesc de nu iau ultimele 6 teste ?
Trebuie facut pe numere mari ? (desi nu cred , ca nu mai intra in timp)

[•bogdan2412]

Asa faceam si eu aria si nu-mi lua ultimele 6 teste. Dupa asta am facut aria cu metoda de pe TopCoder:

Cod:

    long x1,x2,y1,y2;
    for(i=1;i+1<n;i++)
    {
        x1=v[i].x-v[0].x;
        y1=v[i].y-v[0].y;
        x2=v[i+1].x-v[0].x;
        y2=v[i+1].y-v[0].y;
        S+=(double)x1*y2-(double)x2*y1;
    }
    S=fabs(S*0.5);

si a mers. Nu cred totusi ca asta era problema. Mai probabil era ca am gresit la implementare.

[•sarabogdan]

Am incercat sa calculez asa si tot 40 iau
Mersi oricum