[ BIHacker @ 07.01.2004. 11:39 ] @

U ravni se nalazi poligon čije su stranice paralelne s koordinatnim osima, a x i y koordinata bilo kojeg vrha je cijeli broj.
Potrebno je izračunati površinu tog poligona.Broj vrhova je <=1000.Kordinate su cijeli brojevi cija je apsolutna vrijednost <=10 000.
[ leka @ 09.01.2004. 02:46 ] @
Iako je ovo interesantan problem, ja zaista moram da napomenem da ovo
nije mesto gde osoba X (uglavnom osoba koja je postala ES clan samo zato
jer nikako drugacije nije mogla da resi problem) postavi problem, a
osoba Y (uglavnom mazohista, dugogodisnji clan ES-a) joj taj problem
resava...
Nemoj me pogresno shvatiti, ali mesecima (godinama) gledam istu pricu.
Zasto nisi napisao kakvo-takvo resenje u bilo kojem jeziku, nema veze da
li radi ili ne radi, pa da onda diskutujemo? Ovako ja (a verujem i neki
drugi ljudi) prosto nemam motivaciju da ti pomognem, jer mi NISTA ne
govori da si se makar malo potrudio da problem sam resis...
[ noviKorisnik @ 09.01.2004. 07:56 ] @
Da onda pomažemo na kašičicu?

Imaš skup s <= 1000 elemenata. Elementi skupa su uređeni celobrojni parovi brojeva apsolutno <= 10000.

Ovaj skup određuje figuru u ravni na način koji si opisao, i to jednoznačno (hm, čini mi se da je tako).

... kašičica iscurila...

I sad, kako doći do površine?
[ degojs @ 09.01.2004. 20:39 ] @
Postoji formula po kojoj se jednostavno računa površina bilo kog poligona (stranice nisu nužno paralelne sa osama). Za formulu možeš da pitaš bilo kog studenta koji ima veze sa npr. geodezijom. E, sad je već malo više do tebe pošto imaš iz ovih poruka odakle da kreneš.
[ filmil @ 10.01.2004. 02:00 ] @
http://geometryalgorithms.com/...gorithm_0101.htm#2D%20Polygons

f
[ Mihailo Kolundzija @ 10.01.2004. 19:15 ] @
Citat:

"BIHacker" wrote:
>
> U ravni se nalazi poligon čije su stranice paralelne s koordinatnim osima, a x i y koordinata bilo kojeg vrha je cijeli broj.
> Potrebno je izračunati površinu tog poligona.Broj vrhova je <=1000.Kordinate su cijeli brojevi cija je apsolutna vrijednost <=10 000.



Evo do čega sam došao (pretpostaviću da imaš koordinate duži koje
obrazuju poligon (znači, da si pospajao one vrhove kako treba)):

Code:

  sortiraš x koordinate svakog temena u rastući poredak (pritom bi bilo dobro da za svaki element ukloniš njegove duplikate (ako ih ima)). Nazovimo taj niz x
  sortiraš sve duži paralelne sa x osom u rastućem redosledu po y koordinati
  postavi ukupnu površinu na nulu
  za svaki par (x[i], x[i+1]), i = 1 do veličina(x)-1
    postavi brojač na nulu
    kreneš kroz (sortiran) niz duži paralelnih sa x osom
     ako duž seče traku (x[i], x[i+1])
       povećaš brojač za jedan
        ako je brojač neparan
          zapamti y koordinatu date duži (yp = y)
        u suprotnom (ako je paran)
          dadaj ukupnoj površini vrednost (x[i+1]-x[i]) * (y - yp), gde je y vrednost y koordinate trenutne duži


Ukratko, x koordinate temena se sortiraju u rastućem poretku tako da se
dobiju trake paralelne y osi sa koordinatama (x, x[i+1]) u kojima
nema drugih temena figure. Kakva god da je ta figura, ona sa datom
trakom ima preseke u vidu disjunktnih pravougaonika. Ti pravougaonici se
dobijaju prolaskom kroz sortiran niz ivica paralelnih sa x osom.
Polazeći od prve od njih koja seče traku, svaka druga predstavlja donju
ivicu presečnog pravougaonika, dok "parne" (svaka druga polazeći od
druge koja seče datu traku) predstavlja gornju ivicu presečnog
pravougaonika. Sabiranjem površina tih pravougaonika za svaku traku,
dobija se i površina figure.
(ovo sve pod uslovom da je figura zadata korektno, bez nekih
samopresecanja, poklapanja ivica i sličnih neregularnosti)


[ filmil @ 10.01.2004. 20:55 ] @
Citat:

Code:

sortiraš x koordinate svakog temena u rastući poredak (pritom bi bilo
dobro da za svaki element ukloniš njegove duplikate (ako ih ima)).
Nazovimo taj niz x



Mislim da smo ovim već podigli složenost na , dok je korišćenje polovine vektorskog proizvoda (iz onog
dokumenta) (n broj temena), i povrh toga otporno
je na samopresecajuće ne-paralelne stranice i ne-celobrojne koordinate
temena.

Da ne bude zabune, dopada mi se ideja sasvim, ali sam prilično ubeđen da
bez nekog ne vredi da odgovaramo na pitanje.
E sad druga je priča kako to izvesti. Ništa mi ne pada na pamet; vidim
da nigde nisam upotrebio paralelnost i celobrojnost.

f
[ BIHacker @ 11.01.2004. 19:07 ] @
Hvala svima na pomoci i takodje i na kritikama. Uspio sam rjesiti problem.Evo rjesenja u C-u
Code:


#include <stdio.h>

#define MAX_VRHOVA 10000

int broj_vrhova;
long povrsina;

struct {
         int x,y;
       } vrhovi[MAX_VRHOVA + 1];

void ucitaj_podatke(void)
{
  int i;
  FILE *fp;

  fp = fopen("LIK.IN","rt");

  fscanf(fp,"%d",&broj_vrhova);

  for (i = 0;i < broj_vrhova;++i)
    fscanf(fp,"%d%d",&vrhovi[i].x,&vrhovi[i].y);

  vrhovi[broj_vrhova] = vrhovi[0];

  fclose(fp);
}

void rijesi(void)
{
  int i;

  povrsina = 0l;

  for (i = 0;i < broj_vrhova;++i)
    if (vrhovi[i].y == vrhovi[i + 1].y)
      povrsina += ((long) vrhovi[i].y) * (vrhovi[i].x - vrhovi[i + 1].x);

  if (povrsina < 0l)
    povrsina = -povrsina;
}

void zapisi_rjesenje(void)
{
  FILE *fp;

  fp = fopen("LIK.OUT","wt");

  fprintf(fp,"%ld\n",povrsina);

  fclose(fp);
}

int main(void)
{
  ucitaj_podatke();
  rijesi();
  zapisi_rjesenje();

  return 0;
}
[ degojs @ 11.01.2004. 19:54 ] @
Kako vidim, to je baš ona formula koja se koristi u npr. geodeziji, mada čini mi se da bi još trebao da površinu na kraju podeliš sa 2?
[ zi:: @ 12.01.2004. 12:53 ] @
Problem sa ovim algoritmom:

koji je inače sjajan i jednostavan je u preciznosti. Ukoliko su koordinate velike, lako može da pređe MAXINT, a ukoliko su necelobrojne greška zna jako da poraste.

Ukoliko je za kasnije predloženu implementaciju (long int) dovoljan, onda sve OK. ali šta bi
bilo kada bi koordinate išle od 0 do milion? Nigde nije iskorištena činjenica da su stranice
paralelne sa osima.

Razmišljao sam o dekompoziciji tog poligona na jednostavne pravougaonike, no ne verujem
da postoji O(n) algoritam koji to radi.
[ Mihailo Kolundzija @ 15.01.2004. 23:33 ] @
Citat:

> Mislim da smo ovim već podigli složenost na , dok je korišćenje polovine vektorskog proizvoda (iz onog
> dokumenta) (n broj temena), i povrh toga otporno
> je na samopresecajuće ne-paralelne stranice i ne-celobrojne koordinate
> temena.
>
> Da ne bude zabune, dopada mi se ideja sasvim, ali sam prilično ubeđen da
> bez nekog ne vredi da odgovaramo na pitanje.
> E sad druga je priča kako to izvesti. Ništa mi ne pada na pamet; vidim
> da nigde nisam upotrebio paralelnost i celobrojnost.


Primedba je na mestu. Pošto uglavnom radim po principu "piši kad hoćeš,
šalji kad možeš", nisam video ono što si poslao u vreme sastavljanja i
slanja one poruke.