Задача 3. Медали
Петя развесил на стене в своей комнате полученные на
соревнованиях медали и пояса. Мама предложила Пете найти такие две медали,
чтобы протянутый через них пояс был параллелен наибольшему числу развешенных
поясов. Считается, что пояса развешены жестко без прогибов.
Формат входных данных:
В первой строке входного файла MEDALS.INI задано количество медалей
(N
>= 2). Далее заданы координаты медалей X и Y (по одной медали в каждой
строке), разделенные пробелом. Затем следует строка задающая количество поясов.
После нее заданы координаты начала и конца каждого пояса, разделенные пробелом
(по одному поясу в каждой строке).
Формат выходных данных:
В первой строке выходного файла MEDALS.OUT выведено число
найденных поясов, параллельных поясу, протянутому через найденные 2 медали.
Далее координаты этих медалей, по одной медали в каждой строке. Если таких
вариантов несколько вывести все.
STARS.INI
|
STARS.OUT
|
3
2 3
0 4
5 3
3
3 0 0 0
4 6 7 6
3 1 9 1
|
3
2 3
5 3
|
Решение на языке Pascal
program
medali;
var
f:text;
n,m:byte;
xm,ym:array[byte] of integer;
x1p,x2p,y1p,y2p:array[byte] of integer;
xp,yp:array[byte] of integer;
i,j,k,max:byte;
kol:array[1..100,1..100] of integer;
BEGIN
assign(f,'stars.ini');
Reset(f);
Readln(f,n);
for
i:=1 to n do
begin
Read(f,xm[i]);
Readln(f,ym[i]);
end;
Readln(f,m);
for
i:=1 to m do
begin
Read(f,x1p[i]);
Read(f,y1p[i]);
Read(f,x2p[i]);
Readln(f,y2p[i]);
xp[i]:=x2p[i]-x1p[i];
yp[i]:=y2p[i]-y1p[i];
end;
Close(f);
for
i:=1 to n-1 do
for
j:=i+1 to n do
begin
for
k:=1 to m do
if
xp[k]*(ym[i]-ym[j])=yp[k]*(xm[i]-xm[j]) then
begin
kol[i,j]:=kol[i,j]+1;
end;
if
kol[i,j]>max then max:=kol[i,j];
end;
Assign(f,'stars.out');
Rewrite(f);
for
i:=1 to n-1 do
for
j:=i+1 to n do
if
kol[i,j]=max then
begin
writeln(f,max);
write(f,xm[i]);writeln(f,ym[i]);
write(f,xm[j]);writeln(f,ym[j]);
end;
Close(f);
END.
Замечание. В
случае если файл stars.ini не создан, программа выдаст
ошибку.
|