[es] - Povrsina figure!

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.

Profil

^{07.01.2004. u 11:39 - pre 247 meseci}

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.

nix

Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.231.216.81.gus.vf.siwnet.net

Sajt: dejan.lekic.org

+2 Profil

Re: Povrsina figure!

^{09.01.2004. u 02:46 - pre 247 meseci}

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...

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.bankmeridian.com

Sajt: www.novikorisnik.net

+5 Profil

Re: Povrsina figure!

^{09.01.2004. u 07:56 - pre 247 meseci}

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?

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Odgovor na temu

degojs

Član broj: 4716
Poruke: 5096

+51 Profil

Re: Povrsina figure!

^{09.01.2004. u 20:39 - pre 246 meseci}

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š.

Commercial-Free !!!

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Povrsina figure!

^{10.01.2004. u 02:00 - pre 246 meseci}

http://geometryalgorithms.com/...gorithm_0101.htm#2D%20Polygons

f

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.dialup.ns.ac.yu

+1 Profil

Re: Povrsina figure!

^{10.01.2004. u 19:15 - pre 246 meseci}

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)

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Povrsina figure!

^{10.01.2004. u 20:55 - pre 246 meseci}

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

Odgovor na temu

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.

Profil

Re: Povrsina figure!

^{11.01.2004. u 19:07 - pre 246 meseci}

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;
}

nix

Odgovor na temu

degojs

Član broj: 4716
Poruke: 5096

+51 Profil

Re: Povrsina figure!

^{11.01.2004. u 19:54 - pre 246 meseci}

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?

Commercial-Free !!!

Odgovor na temu

zi::
Igor Marinović
Manufaktura doo Internet inženjering
Palić

Član broj: 18090
Poruke: 642
*.tippnet.co.yu.

ICQ: 7715569
Sajt: www.marinowski.com

Profil

Re: Povrsina figure!

^{12.01.2004. u 12:53 - pre 246 meseci}

Problem sa ovim algoritmom:

Citat:

http://geometryalgorithms.com/...gorithm_0101.htm#2D%20Polygons

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.

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.dialup.ns.ac.yu

+1 Profil

Re: Povrsina figure!

^{15.01.2004. u 23:33 - pre 246 meseci}

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.

Odgovor na temu