Z-prave

program mi prolazi samo na prvom test primjeru ;D
pa bih molio barem jedan test primjer!

To da ne davis ljude po forumu idejom :) ?

10
1 1
2 3
3 4
5 6
7 8
9 10
11 12
12 14
14 15
16 16


23

hvala...ne prolazi na njemu, pa idem ttražit grešku

Ja sam rjesio z-prave i rade u vremenu, al stalno mi padaju na 7. primjeru i zadnjih 5 primjera.
Isprobao sam sve moguce primjere i sta god napisem mi dobro vraca, al kad uploadam eto ti mi padaju, a cini mi se da sam pokrio sve moguce iznimke i stvarno ne znam zasto pada. Jel bi mogo i meni dati neki gadni test primjer jer ja vise ne znam koji da izmislim. hvala

Koje iznimke?

Ti si verovatno racunao neke uglove, delio (pa pazio na deljenje sa nulom) i sl....

Znas kako sam ja odradio? Za sve parove tacaka racunao K i N (ono iz implicitnog oblika jednacine prave) i u svakoj iteraciji proveravao imam li ih u skupu dosad nadjenih K i N. Ako nemam, ubacim taj par (K,N) u skup i povecam brojac resenja, koji na kraju ispisem.

Nema nikakvih specijalnih slucajeva, sve kalkulacije staju u longint, N je dovoljno malo pa moze da se "ugura" u O(n^2)... Milina od zadatka, jedan od retkih koji mi je prosao iz prvog pokusaja. ;D

Ako ne znas (i ne mozes da nadjes na netu) formule za kacunanje vrednosti K i N, javi se.

P.S.
- K je tacno jednak tg(A), gde je A ugao koji prava gradi sa X osom
- N odsecak na Y osi (tacka koja pripada pravoj, a Y koordinata joj je 0)

Srecno!

nisam bas shvatio kako si ti radio, al mislim da je to isto ko moje. ja sam za svaki par tocaka racuno jednadzbu njihovog pravca, tj pamtio sam samo b i c iz y = bx + c. Onda sam samo pobriso iste i vratio velicinu vektora. Ali ipak pada mi na tim nekima.

A zasto si brisao elemente iz vektora????

Hm, ondmah da ti kazem da i nisam neki matematicar, ali koliko znam taj oblik prave sto si napisao je isti oblik o kome sam ja govorio, samo sa drugacijim oznakama neko kod mene.

Naime, prava ima dva oblika:
- eksplicitni ( y = k*x + n )
- implicitni ( a*x + b*y + c = 0 )

Prvi slucaj (eksplicitni oblik) ti je objasnjen na kraju moje prethodne poruke, samo sto bih dodao da je
k=(y2-y1) / (x2-x1)
n=(x2*y1-x1*y2) / (x2-x1)

U drugom slucaju:
a = y1-y2
b = x2-x1
c = x1*y2 - x2*y1

E sad, bilo koji oblik od ova dva da izaberes, moci ces pomocu dva (u ekplicitnom) ili tri (u implicitnom) obliku jednoznacno da odredis sve prave koje mozes da povuces. Mozes, znaci, i da pamtis {a,b,c} kao skup od tri clana koji odredjuje jednu pravu, pa da uzvjek racunas imas li trenutno {a',b',c'} u tvom skupu nadjenih vrednosti. Ako nemas, dodas te tri vrednosti i uvecas brojac resenja. Ako imas, nikom nista, jer znaci da te dve tacke za koje se izracunao a', b' i c' leze na pravoj koju si vec izbrojao (koju grade neke druge dve tacke koje si proverio pre trenutnih)...

Znaci pametnije ti je da pamtis K i N nego A, B i C jer u prvom slucaju pamtis manji broj vrednosti a i lakse je za implementaciju.

Nadam se da si shvatio... ;)

program prekoračuje vremensko ograničenje na 18. i 20. test primjeru, znači na 2 test primjera,

evo kod:

const INF=650000000.123456;
var n,np,i,j,l:integer;
ima:boolean;
kx,by:double;
x,y:array[1..105] of integer;
k:array[1..11000] of double;
t:array[1..11000] of integer;
function nagib(g,h:integer):double;
begin
if abs(x[g]-x[h])=0 then nagib:=INF else nagib:=abs((y[g]-y[h])/(x[g]-x[h]));
end;
begin
readln(n);
np:=0;
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n-1 do
for j:=i+1 to n do begin
ima:=false;
kx:=nagib(i,j);
for l:=1 to np do begin
if (l<>i) and (abs(kx-k[l])<0.000000001) and (abs(nagib(i,t[l])-kx)<0.000000001) then begin ima:=true; break; end;
if (l<>j) and (abs(kx-k[l])<0.000000001) and (abs(nagib(j,t[l])-kx)<0.000000001) then begin ima:=true; break; end;
end;
if not ima then begin
inc(np);
k[np]:=kx;
t[np]:=i;
end;
end;
writeln(np);
readln;
end.

išao sam za svaki par točaka naći nagib pravca i provjeravao da li već imam takav pravac, ako ne onda ga dodam na listu i to je to...

probaj ovo

const INF=650000000.123456;
var n,np,i,j,l:integer;
ima:boolean;
kx,by:double;
x,y:array[1..105] of integer;
k:array[1..11000] of double;
t:array[1..11000] of integer;
function nagib(g,h:integer):double;
begin
if x[g]=x[h] then nagib:=INF else nagib:=abs((y[g]-y[h])/(x[g]-x[h]));
end;
begin
readln(n);
np:=0;
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n-1 do
for j:=i+1 to n do begin
ima:=false;
kx:=nagib(i,j);
for l:=1 to np do begin
if abs(kx-k[l])<0.000000001 then
  begin
		if (l<>i) and (abs(nagib(i,t[l])-kx)<0.000000001) then begin ima:=true; break; end;
		if (l<>j) and (abs(nagib(j,t[l])-kx)<0.000000001) then begin ima:=true; break; end;
	end;
end;
if not ima then begin
	inc(np);
	k[np]:=kx;
	t[np]:=i;
end;
end;
writeln(np)
end.

hvala puno, prošlo je..