Uzmi proizvoljnu tačku za koju si siguran da se ne nalazi u datom liku (na primjer tacka Z[maxX+1][maxY+1], gdje su maxX i maxY najvece koordinate koje se pojavljuju u tackama koje opisuju zadano tijelo), i zatim spoji tako dobijenu tacku sa tackom koja ti je zadana. Te dve tacke spojene daju duz. Ako je broj ivica koje tako dobijena duz sjece paran, tacka se nalazi izvan lika, a ako nije, tacka se nalazi unutar tog lika. Evo ti i primjer programa koji određuje da li se 2 duzi sijeku... Ostatak je lak.
Code:
#include <iostream>
#include <fstream>
using namespace std;
struct tacka
{
int x;
int y;
};
struct duz
{
tacka poc;
tacka kraj;
};
int saIsteStr (duz p, tacka C, tacka D);
int intersect (duz d1,duz d2);
int main(int argc, char *argv[])
{
ifstream in ("c:\\intersect.txt");
tacka A,B,C,D;
in >> A.x >> A.y;
in >> B.x >> B.y;
in >> C.x >> C.y;
in >> D.x >> D.y;
in.close();
duz d1,d2;
d1.poc=A; d1.kraj=B;
d2.poc=C; d2.kraj=D;
if (intersect(d1,d2))
cout << "sijeku se\n";
else
cout << "ne sijeku se\n";
system("PAUSE");
return EXIT_SUCCESS;
}
int intersect (duz d1,duz d2)
{
if ( (saIsteStr(d1,d2.poc,d2.kraj) ) &&
(saIsteStr(d2,d1.poc,d2.kraj) ) )
return 1;
return 0;
}
int saIsteStr (duz p, tacka C, tacka D)
{
/*
rez<0 ==> tacke C i D su sa suprotnih strana duzi p
rez=0 ==> jedna od tacaka lezi na duzi p
rez>0 ==> tacke C i D su sa istih strana duzi p
*/
int dx,dy,dx1,dx2,dy1,dy2, rez;
dx=p.kraj.x-p.poc.x;
dy=p.kraj.y-p.poc.y;
dx1=C.x-p.poc.x;
dy1=C.y-p.poc.y;
dx2=D.x-p.kraj.x;
dy2=D.y-p.kraj.y;
rez=(dx*dy1-dy*dx1)*(dx*dy2-dy*dx2);
if (rez>0)
return 0;
else
return 1;
}
@Toroman: Evo, uradio sam zadacu!!! :-)
[Ovu poruku je menjao peromalosutra dana 15.04.2006. u 22:54 GMT+1]