Графическая задача Опции

[Tribunal]

Задача такова:
Дан файл вещественных чисел,которые являются координатами точек.
Нужно найти такие 3 точки, что треугольник, построенный на этих точках
будет содержать максимальное количество точек множества.
Координаты этих трёх точек сохранить в файле, как результат
+нужна графическая иллюстрация к этой задаче.

Предложите,пожалуйста,варианты решения этой задачи или какие-нибудь идеи.
У меня они пока не могут оформиться...

Буду благодарна за помощь.

Сообщение отредактировано: Tribunal - 13.05.2006 19:02

[мисс_граффити]

как узнать, принадлежит ли точка треугольнику - есть здесь:
http://algolist.manual.ru/olimp/geo_prb.php

а в целом....
перебором, наверное. для каждых 3 точек считать, сколько точек будет внутри этого треугольника. если больше, чем хранящееся в переменной max значение - запоминать точки.
надеюсь, проблем с чтением из файла и с записью в него нет?

иллюстрация... тут придется координаты округлять. или брать масштаб побольше, а потом все равно округлять - Паскаль при рисовании любит целочисленные.

[Tribunal]

а для того,чтобы координаты можно было редактировать(изменять,удалять),их лучше считать из файла в список?

и всё же мне не очень понятьно,как перебирать разные треуголники и при этом делать проверку на кол-во точек...(( может кто-нибудь помочь разобраться?...(

[Malice]

Где-то вот так:

max:=0; t1_max:=1; t2_max:=2;  t3_max:=3; 
for t1:=1 to n-2 do {точка 1}
   for t2:=t1+1 to n-1 do  {точка 2}
    for t3:=t2+1 to n do begin {точка 3}
попал=0;
for x:=1 to n do begin {перебор всех точек}
if Принадлежит (x, t1,t2,t3) then inc (попал);
end;
if попал>max then begin max:=попал; t1_max:=t1; t2_max:=t2;  t3_max:=t3;  end;
end;

можно еще добавить проверку, чтоб x был не равен t1,t2,t3.

[Tribunal]

я решила считывать координаты из файла в список.
вот,что получилось,но появляется ошибка: invalid numeric input

type
    t_ptr=^t_element;
    t_element=
      record
       infx:real;
       infy:real;
       next:t_ptr;
      end;

var
   f:text;
   x,y:real;
   i,n,k:byte;
   first,pos:t_ptr;
begin
assignfile(f,'position.txt');
readln(n);

reset(f);
repeat
  new(first);
  first^.next:=nil;
  readln(f,x,y);
  first^.infx:=x;
  first^.infy:=y;
  for i:=1 to n-1 do
   begin
     new(pos);
     readln(f,x,y);
     pos^.infx:=x;
     pos^.infy:=y;
     pos^.next:=nil;
     pos^.next:=first;
     first:=pos;
     inc(k);
   end;
until (eof(f)) or (k=n-1);
close(f);

в файле записаны вещ-ные числа таким образом:
40,5 8
26,4 5,099

[Бродяжник]

Если они записаны именно таким образом, то замените запятую на точку.

И потом, что значит вот это:

pos^.next:=nil;
pos^.next:=first;

Зачем присваивать nil, если это значение все равно будет тут же утеряно?

[мисс_граффити]

может, я не права, но... не логичнее ли работать с типизированным, а не тестовым файлом?
имхо, "файл вещественных чисел"(по условию) - не text, а file of real.

[Tribunal]

нет.я не написала в условии,
но сказано работать с текстовым файлом.

[Tribunal]

значит у меня получается вот какая штука:
есть файл координат, которые в свою очередь находятся в списке для обработки.
я хочу сделать так,чтобы можно было изменять координаты конкретной точки,то есть по ее номеру.
процедура,которая у меня получилась почему-то очищает файл...(
почему?подскажите,пожалуйста...

Код

var
   xe,ye:real;
   ne,k:byte;
begin
writeln('Введите x');read(xe);
writeln('Введите y');read(ye);
writeln('Введите n');read(ne);

assign(f,'position.txt');
rewrite(f);
if ne>kol then writeln('Такой координаты нет.Добавьте.')
else begin
pos:=first;
k:=1;
while (pos^.next<>nil) and (not eof(f))  do
if k=ne then begin
pos^.infx:=xe;
pos^.infy:=ye;
writeln(f,pos^.infx,pos^.infy);
end
else begin
inc(k);
pos:=pos^.next;
readln;
end;
end;
close(f);

Сообщение отредактировано: Tribunal - 16.05.2006 10:05

[volvo]

Tribunal, все правильно... Только файл не "очищается", а НЕ создается... Смотри:

assign(f,'position.txt'); rewrite(f); { ты затерла файл новым, пустым... }

if ne>kol then writeln('Такой координаты нет.Добавьте.')
else begin
  pos:=first;
  k:=1;
  while (pos^.next<>nil) and (not eof(f))  do { Все, дальше неважно...}
...

А неважно - потому, что там, где я поставил комментарий у тебя при первом же проходе УЖЕ достигнут конец файла (файл-то пустой), и ничего выполняться, естественно, не будет...

[Tribunal]

а как тогда мне изменить файл?

[volvo]

Что-то типа:

writeln('Введите x');read(xe);
writeln('Введите y');read(ye);
writeln('Введите n');read(ne);

assign(f, 'position.txt'); rewrite(f);

pos := first;
{ ищешь в СПИСКЕ точку с нужным номером }
while (pos <> nil) and (ne > 0) do begin
  pos := pos^.next; dec(ne);
end;

{ если NE = 0, значит точка с заданным номером есть в списке }
if ne = 0 then begin
  pos^.infx:=xe;
  pos^.infy:=ye;
  { ... И теперь сохранять ВЕСЬ список в файл ... }
  pos := first;
  while pos <> nil do begin
    writeln(f,pos^.infx,pos^.infy);
    pos := pos^.next;
  end;
  close(f);
  { Сохранено ... }
end
else
  writeln('Введенный номер точки больше, чем их общее количество.');

Набирал прямо здесь - могут проявиться глюки. Но идея у меня именно такая...

[Tribunal]

...эээ...проблема в том,что когда я записываю из файла
в список координаты,я записываю не весь файл,а задаваемое число координат...
поэтому при редактировании в файл записывается только та часть,которая была в списке.
можно ли сделать,чтобы редактировалась только часть файла,а остальное оставалось на месте?
и вообще целесообразно ли для этого использовать списки?

[volvo]

Нет... Для того, чтобы отредактировать текстовый файл, его надо редактировать полностью... Текстовый файл - файл с последовательным доступом...

Ты не можешь изменить только середину файла, не трогая всего остального.

[Tribunal]

а тогда можно ли в моем случае это сделать как-то иначе?
может стоит остаток файла записывать в еще один список?

[мисс_граффити]

а если все несколько упростить - предположить, что количество точек заранее известно.
соответственно, работать не со списками, а с массивом... все, что идет после интересующего кол-ва точек - игнорировать.

[Tribunal]

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

[Tribunal]

а что обозначает сие выражение?

if Принадлежит (x, t1,t2,t3) then inc (попал);

[Malice]

а что обозначает сие выражение?

if Принадлежит (x, t1,t2,t3) then inc (попал);

Это значит, что нужно определить эту функцию (название конечно не русское будет, я для примера написал), которая будет проверять вхождение точки х в треугольник t1,t2,t3. И если принадлежит - прибавить счетчик.

[Tribunal]

а,ну тогда ясно...