Алгоритм для Задачи, нужны умники

[gse44]

Целочисленная точка (x, y) в первом квадранте (x >= 0, y >= 0, x + y > 0) называется видимой, если на отрезке (0, 0) - (x, y) не лежит никакой другой целочисленной точки. Например, точка (4, 2) не является видимой, так как на отрезке (0, 0) – (4, 2) лежит точка (2, 1). Ваша задача – подсчитать количество видимых точек (x, y), удовлетворяющих условию *x, y <= N.
Входные данные.
Во входном файле записано целое число N (1 <= N <= 1000).

Запишите в выходной файл найденное количество видимых точек.

Примеры:
visible.in visible.out
2 5
4 13
5 21
231 32549


Сам алгоритм нахождения целочисленных точек я составил, например на паскале:

k //Количество решений
x, y //Координаты

for x:=1 to n do
do
y:=y+1;
k:=k+1;
while (y<x) and (x<n) //Т.к. логично разделить плоскость биссектрисой осей y=x, а потом умножить количество решений на 2
k:=k*2+3; //3 точки всегда будут целочисленными в начале

Теперь вопрос: как проверить не лежат ли еще точки на одной прямой, чтобы не брать их в решение...

+ ограничение на выполнение 1сек. хотя думаю, это можно проаппелировать

[p51x]

составить уравнение прямой y=kx+b по двум точкам (0,0) и (x,y)
быстренько пробежать или прикинуть...

[gse44]

Я тоже так думал, через while внутри первого while

X1:=x;
do
X1:=X1-1
For здесь весь предыдущий цикл!
While ....

Но представьте сколько программа будет выполняться, если n введут 1000 или больше....

Каждый раз придется туда, потом обратно его гонять для каждой координаты

Может для каждой целочисленной точки составлять уравнение прямой и сверять с уже созданными уравнениями, если таких уравнений нет, то кол решений +1 ?

Как это сделать?

[p51x]

Каждый раз придется туда, потом обратно его гонять для каждой координаты

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

[Kingdom_Reborn]

Сообщение от p51x

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

так эту задачу не решить - по времени точно не прокатит...

Я тут немного подумал над задачкой и пришла в голову мысль...
Количество видимых точек равно количеству различных прямых, которые можно провести через все эти точки. И сразу такая идея: прямые можно различать по угловому коэффициенту k... и далее развиваю мысль: считаем угловые коэффициенты для каждой точки (т. е. угловой коэффициент прямой, проходящей через эту точку), сортируем все эти коэффициенты и запросто считаем количество различных прямых!
Начал это реализовывать и получилось, что при n = 1000 алгоритм работает долго. Улучшаю: делю всю область точек (а это квадрат) на две (по прямой y = x), и считаю количество точек в одной из областей, а потом умножаю на 2. Всё равно работает долго... Ну что ж, опять делю область на 2 (по прямой y = -x + n) и в итоге всё умножаю на 4. Теперь получился алгоритм, который укладывается в 1 секунду при n = 1000 и выдаёт правильный результат .

Выставляю код на общую критику:

program Project2;

{$APPTYPE CONSOLE}
{$MAXSTACKSIZE 10000000}
{$R+ $Q+ $S+}

uses
  SysUtils;

type
  TArray = Array[1..500000] of Double;

procedure Swap(var X, Y: Double);
var
  tmp: Double;
begin
  tmp := X;
  X := Y;
  Y := tmp;
end;

function Medium(const A, B: Integer): Integer;
begin
  Randomize;
  Medium := A + Random(B - A + 1);
end;

function Partition(const A, B: Integer; var X: TArray): Integer;
var
  K: Double;
  M, L, R: Integer;
begin
  L := A - 1;
  R := B + 1;
  M := Medium(A, B);
  K := X[M];
  while True do
  begin
    repeat
      Inc(L);
    until X[L] >= K;
    repeat
      Dec(R);
    until X[R] <= K;
    if L < R then Swap(X[L], X[R]) else Break;
  end;
  Partition := R;
end;

procedure QuickSort(const a, b: Integer; var X: TArray);
var
  L: Integer;
begin
  if A < B then
  begin
    L := Partition(a, b, X);
    Quicksort(a, L, X);
    Quicksort(L + 1, b, X);
  end;
end;

function Solve(const n: Integer): Integer;
var
  k, q, i, x, y: Integer;
  P: TArray;
begin
  k := 0;
  for y := 1 to n do
    for x := y to n - y do
    begin
      Inc(k);
      P[k] := y / x;
    end;
  QuickSort(1, k, P);
  q := 0;
  i := 1;
  while i <= k do
  begin
    Inc(q);
    while (i < k) and (Abs(P[i] - P[i + 1]) < 1e-6) do
      Inc(i);
    Inc(i);
  end;
  Solve := q * 4 + 1;
end;

var
  n: Integer;
begin
  Reset(Input, 'visible.in');
  Rewrite(Output, 'visible.out');
  ReadLn(n);
  WriteLn(Solve(n));
end.

А область может быть ещё множно поделить

P. S. при подсчёте не учитываются точки (1, 0) и (0, 1), поэтому к результату нужно добавить 2. Но так как точка (1, 1) считается два раза, то добавляем 1.

P. P. S. Алгоритм конечно очень сомнительный в плане производительности, и решается эта задача наверняка другим способом.
Были мысли о вращении луча на угол от 0 до 90 градусов... Вращать его нужно до ближайшей точки. В итоге количество поворотов это и был бы ответ, но как это реализовать я не знаю

А можно было бы рассчитать точность этих k при n = 1000. Тогда можно было бы придумать хеш-функцию и заносить все k в хеш-таблицу... Хотя это бредовая идея...

[Sasha_Smirnov]

3 точки (x1; y1), (x2; y2), (x3; y3) лежат на прямой, если они не образуют треугольник.

Можно по координатам сосчитать площадь* (не равна ли она нулю), а можно сравнивать суммы длин двух сторон с третьей...

[Sibedir]

Kingdom_Reborn +

Можно еще

 for y := 1 to n do
    for x := (y+1) to n - y do

[evg_m]

function NODisONE(a,b: integer): integer;// определение наибольшего общего делителя
begin // для наших целей достаточно знать =1 >1
//если NOD =k >1, то точка (a div k, b div k) будет закрывать нашу точку (a,b)
end;

s:=3; // это три прямые (вертикаль горизонталь диагональ), которые в нашем подсчете не будут участвовать изначально
for j:=1 to N do
begin  
  // проверка точех вида (*,j)  на вертикали j  до диагонали
  for x:=1 to j-1 do //=1 не учитывать горизонталь  j-1 не учитывать диагональ
    if NODisONE(x,j) then s:=s+1;
  // проверка точех вида (j,*)  на горизонтали  j  до диагонали
  for y:=1 to j-1 do //=1 не учитывать вертикаль  j-1 не учитывать диагональ
    if NODisONE(y,j) then s:=s+1;
end;