Diskuze: Sú body na max. svoch priamkách?
Člen
Zobrazeno 11 zpráv z 11.
Jak to zkousis overit? Algoritmus za tim? Pomale pro jak velke vstupy/jak moc radove pomale?
Skúšam to postupným odoberaním z poľa a počítaním jednotkového vektoru pre každý bod. Pomalé je to pri vstupoch s rádovo 10 000 bodmi. Vtedy to trvá viac ako 10 s. S 1 000 bodmi to trvá cca. 1,5 s.
program priamkabody;
{$APPTYPE CONSOLE}
uses
math,sysutils;
type bod=record
x,y:real;
end;
pole=array of bod;
function xround(x:real; miesta:longint):real;
var
del:real;
begin
del:=power(10, miesta);
xround:=round(x*del)/del;
end;
function je(A,B,C:bod):boolean;
var
bx,by:real;
cx,cy:real;
lb,lc:real;
begin
bx:=B.x-A.x;
by:=B.y-A.y;
cx:=C.x-A.x;
cy:=C.y-A.y;
lb:=sqrt(bx*bx+by*by);
lc:=sqrt(cx*cx+cy*cy);
bx:=xround(bx/lb,10);
by:=xround(by/lb,10);
cx:=xround(cx/lc,10);
cy:=xround(cy/lc,10);
je:=((bx=cx) and (by=cy)) or ((bx=-cx) and (by=-cy));
end;
function vyhod(var list:pole; idx:longint):bod;
var
i:longint;
begin
vyhod.x:=0;
vyhod.y:=0;
if idx<length(list) then begin
vyhod:=list[idx];
for i:=idx to length(list)-2 do list[i]:=list[i+1];
setlength(list,length(list)-1);
end;
end;
var
i,j,n,priamky:longint;
list,pole2:pole;
A,B:bod;
begin
readln(n);
for i:=1 to n do begin
setlength(list,length(list)+1);
with list[length(list)-1] do readln(x,y);
end;
priamky:=0;
for i:=1 to length(list)-1 do begin
pole2:=copy(list,0,length(list));
priamky:=1;
B:=vyhod(pole2,i);
A:=vyhod(pole2,0);
for j:=length(pole2)-1 downto 0 do if je(A,B,pole2[j]) then vyhod(pole2,j);
if length(pole2)=0 then break;
priamky:=2;
A:=vyhod(pole2,0);
B:=vyhod(pole2,0);
for j:=length(pole2)-1 downto 0 do if je(A,B,pole2[j]) then vyhod(pole2,j);
if length(pole2)=0 then break;
priamky:=3;
end;
if priamky <=2 then writeln('ANO')
else writeln('NIE');
end.Jednoduché řešení je následující:
Ďakujem, skúsim to. Mohol by si prosím trochu rozpísať, čo je smernica vektora?
Vektor vzdálenosti bodu (vektoru) od počátku soustavy normalizovaný na jednotkovou délku.
Me napadlo obecnou rovnici primky v kombinaci s vzorcem pro stanoveni, jestli bod lezi nebo nelezi na primce. Nejspis se stejnou komplexitou jako vyse uvedene reseni.
Tak som to skúsil cez tú smernicu priamky, ale neviem, čo robiť, keď sú body nad sebou (majú rovnakú x súradnicu). Vtedy tam nastáva delenie nulou.
program priamkabody;
type bod=record
x,y:longint;
end;
var
n,i,j,x,y,n2,n3:longint;
body,zvysneBody:array[0..100001] of bod;
vektory:array[0..100001] of real;
k:real;
begin
readln(n);
if n<=4 then begin
writeln('ANO');
halt;
end;
for i:=1 to n do readln(body[i].x,body[i].y);
x:=body[1].x;
y:=body[1].y; //y-y[i]=k*(x-x[i]) //k=(y-y[i])/(x-x[i])
for i:=2 to n do begin
vektory[i]:=(abs);
end;
n2:=0;
k:=0;
for i:=2 to n do begin
if (k=0) then for j:=3 to n do if (vektory[i]=vektory[j]) then
k:=vektory[i];
if (vektory[i]<>k) then begin
n2+=1;
zvysneBody[n2]:=body[i];
end;
end;
if (n2<3) then begin
writeln('ANO');
halt;
end
else begin
x:=zvysneBody[1].x;
y:=zvysneBody[1].y;
for i:=2 to n2 do vektory[i]:=(abs);
n3:=0;
k:=0;
for i:=2 to n2 do begin
if (k=0) then for j:=3 to n2 do if (vektory[i]=vektory[j]) then
k:=vektory[i];
if (vektory[i]<>k) then begin
n3+=1;
end;
end;
if n3=0 then writeln('ANO')
else writeln('NIE');
end;
readln;
end.
V tom případě, kdy jsou x souřadnice stejné, tedy při výpočtu směrnice bys dělil nulou, tak se tomu říká přímka bez směrnice. Tato přímka je rovnoběžná s osou y a oba body leží na téže přímce.
Uveďme si příklad.
Máme body A=[3;5] a B=[3;7].
Napřed si spočítáme směrový vektor: s=(3-3;7-5)=(0;2).
Ze směrového vektoru si zkusíš spočítat směrnici, jako jsi to dělal do
teď: k=2/0
Nulou však nelze dělit a je to tedy přímka bez směrnice. Tím pádem je to
přímka rovnoběžná s osou y, která prochází bodem 3 na ose x. Zkus si tu
přímku pro lepší představu nakreslit do grafu.
Dobre, čo ale keď je tých priamok bez smernice viac? Ako zistím, ktorá je ktorá?
Všechny body, které mají stejnou souřadnici x, by mohly ležet na jedné
přímce.
Řekněme, že máme body A=[2;5] B=[2;-2] C=[5;3] D=[5;7] E=[1;1]
Body A a B mají stejnou souřadnici y a to 2. Takže body A, B leží na jedné
přímce, která je rovnoběžná s osou y a protíná osu x v bodě 2.
Body C a D to mají podobné. Také tedy leží na stejné přímce.
Avšak bod E neleží na těchto dvou přímkách, a tudíž výstupem programu
by mělo být "NE" (body neleží na dvou přímkách).
Zobrazeno 11 zpráv z 11.