NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Ferko
Člen
Avatar
Ferko:12.10.2017 20:06

Ahoj,
mám problém s jedným programom.

Úlohou je určiť, či ležia body so zadanými súradnicami na dvoch priamkách.

Ako vstup sú zadané súradnice jednotlivých bodov.

Príklad:

Vstup:
0 1
3 4
10 11
5 0
6 2
8 6

Výstup:
'ANO'

Najjednoduchšie je to riešiť tak, že vyberieme ľubovoľné dva body, a skúšame, či na priamke tvorenej týmito bodmi ležia ostatné body.
To je ale pomalé.

Neviete o časovo menej náročnom algoritme, ktorý by riešil tento problém?

Ďakujem

 
Odpovědět
12.10.2017 20:06
Avatar
Neaktivní uživatel
Tvůrce
Avatar
Odpovídá na Ferko
Neaktivní uživatel:12.10.2017 20:10

Jak to zkousis overit? Algoritmus za tim? Pomale pro jak velke vstupy/jak moc radove pomale?

Nahoru Odpovědět
12.10.2017 20:10
Neaktivní uživatelský účet
Avatar
Ferko
Člen
Avatar
Odpovídá na Neaktivní uživatel
Ferko:12.10.2017 20:29

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.
 
Nahoru Odpovědět
12.10.2017 20:29
Avatar
coells
Tvůrce
Avatar
Odpovídá na Ferko
coells:12.10.2017 20:48

Jednoduché řešení je následující:

  1. vyberu si jeden (libovolný) bod X a prohlásím ho za střed soustavy
  2. projedu pole a spočítám směrnici každého vektoru vzhledem k X
  3. seznam směrnic musí obsahovat jedinou hodnotu, která se opakuje, všechny body s touto směrnicí leží na přímce s X
  4. zbylé body leží na druhé přímce, což lze ověřit postupem z bodů 1, 2, 3, které aplikuji na zbylou množinu bodů
 
Nahoru Odpovědět
12.10.2017 20:48
Avatar
Ferko
Člen
Avatar
Odpovídá na coells
Ferko:12.10.2017 20:51

Ďakujem, skúsim to. Mohol by si prosím trochu rozpísať, čo je smernica vektora?

 
Nahoru Odpovědět
12.10.2017 20:51
Avatar
gcx11
Tvůrce
Avatar
Odpovídá na Ferko
gcx11:12.10.2017 20:59

Vektor vzdálenosti bodu (vektoru) od počátku soustavy normalizovaný na jednotkovou délku.

 
Nahoru Odpovědět
12.10.2017 20:59
Avatar
Neaktivní uživatel
Tvůrce
Avatar
Neaktivní uživatel:12.10.2017 22:04

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.

Nahoru Odpovědět
12.10.2017 22:04
Neaktivní uživatelský účet
Avatar
Ferko
Člen
Avatar
Odpovídá na Neaktivní uživatel
Ferko:13.10.2017 19:59

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,zvysneBo­dy: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]:=(ab­s);
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]=vek­tory[j]) then k:=vektory[i];
if (vektory[i]<>k) then begin
n2+=1;
zvysneBody[n2]:=bo­dy[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]:=(ab­s);
n3:=0;
k:=0;
for i:=2 to n2 do begin
if (k=0) then for j:=3 to n2 do if (vektory[i]=vek­tory[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.

 
Nahoru Odpovědět
13.10.2017 19:59
Avatar
Ladislav Ondris
Člen
Avatar
Ladislav Ondris:13.10.2017 23:08

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.

Nahoru Odpovědět
13.10.2017 23:08
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Avatar
Ferko
Člen
Avatar
Odpovídá na Ladislav Ondris
Ferko:15.10.2017 18:08

Dobre, čo ale keď je tých priamok bez smernice viac? Ako zistím, ktorá je ktorá?

 
Nahoru Odpovědět
15.10.2017 18:08
Avatar
Ladislav Ondris
Člen
Avatar
Odpovídá na Ferko
Ladislav Ondris:16.10.2017 0:59

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

Nahoru Odpovědět
16.10.2017 0:59
Pokud neděláš chyby, nepracuješ na dostatečně těžkých problémech.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 11 zpráv z 11.