1052 Timus answer/Решение задачи 1052


№1052
http://acm.timus.ru/problem.aspx?space=1&num=1052
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL

{$N+}
Const
S=0.0001;
Var
X,Y: Array[1..200] of Extended;
N,M,I,J,K,R: LongInt;
Function OnLine(A,B,C: LongInt): Boolean;
Var K,D: Extended;
Begin
If X[A]<>X[B] then begin
K:=(Y[A]-Y[B])/(X[A]-X[B]);
D:=Y[B]-K*X[B];
OnLine:=(abs(Y[C]-(K*X[C]+D))<S);
end else If X[A]=X[C] then Online:=True
else Online:=False;
End;
Begin
M:=0;
Read(N);
For I:=1 to N do
Readln(X[I],Y[I]);
For I:=1 to N do
For J:=1 to N do begin
If I=J then Continue;
R:=0;
For K:=1 to N do
If ((I<>K) and (J<>K)) and OnLine(I,J,K) then Inc(R);
If M<R then M:=R;
End;
Writeln(M+2);
End.

1052. Охота на зайцев

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Хороший охотник убивает двух зайцев одним выстрелом. Конечно же это может быть легко сделано, поскольку через любые две точки можно провести прямую. Но убить трёх и более зайцев одним выстрелом — намного более сложная задача. Чтобы стать лучшим охотником в мире, нужно уметь убить максимально возможное количество зайцев. Представим зайца точкой на плоскости. Точка задаётся целочисленными координатами x и y. Вам нужно найти максимальное число зайцев, которые могут быть убиты одним выстрелом, то есть максимальное количество точек заданного множества, лежащих точно на одной прямой. Никакие два зайца не находятся в одной точке.

Исходные данные

Первая строка ввода содержит целое число N (3 ≤ N ≤ 200) — количество зайцев. Каждая из следующих N строк содержит x и y координаты (в таком порядке), разделённые пробелом (−2000 ≤ x, y ≤ 2000).

Результат

Выведите максимальное число зайцев, находящихся на одной прямой.

Пример

исходные данныерезультат
6
7 122
8 139
9 156
10 173
11 190
-100 1

5
Автор задачи: Станислав Васильев
Источник задачи: Ural State University collegiate programming contest (25.03.2000)
Ярлыки: