Задача на Паскаль: по заданному множеству N точек построить N-угольник

[Dragon65]

|...не прокатит, ибо будет проблема соединения начала и конца...| а в чем проблема, просто соединить начало и конец, в примере,данном в задаче ответ 3 5 4 7 6 1 2 начало и конец- это точки с индексами 3 и 2, а они просто стоят в концах этой последовательности, это разве не опровержение проблемы?) если нет, то я не совсем понял )

MinMax-это максимальные отрицательные либо положительные значения координат точек ?

Когда мы придумываем точку, то координаты вводим сами и соответственно делаем так чтобы не было совпадений.


Если все объединить то одна координата "пробной" точки должна принять Min/Max значений координат данных точек, а вторая координата отличная от координаты данной точки при Min/Max, правильно?

[Аватар]

Слева то, что получится если точку произвольно выбрать, справа если в MinMax

[Dragon65]

т.е min/max это что-то типа среднего арифметического, расстояние между точками. А если точек много, то пробную придется как-то между ними поставить,так?

[Аватар]

MinMax это между минимумом и максимумом по обеим координатам

[Dragon65]

Т.е. взять наибольшие координаты x и y , найти середину между ними и там поставить точку.
Эти координаты можно ввести наверно с помощью readln,завтра попытаюсь составить программу и выложу что получилось)

[Аватар]

Т.е. взять наибольшие координаты x и y

Что за странное мышление

MIN(x)<=x0<=MAX(x)
и
MIN(y)<=y0<=MAX(y)

И их вводить не надо, а програмно вычислить

[ViktorR]

Предположим, что последовательность точек образует многоугольник в форме полумесяца.
И как быть в этом случае?
Может отсортировать по Х и выбрать две самые левые точки (точки лидеры).
Далее для каждой лидирующей точки (а мы выбрали две) выбирать следующие, соотвтетсвующие точки так, что бы линии, соединяющие лидеров с выбранными точками не пересекались. Если на некотором шаге неудается продвинуться, то вернуться на шаг и заменить одну из выбранных точек на следующую.
Еще одно условие: координаты по Х лидирующих точек должны быть либо одинаковыми, либо рядом. Т.о. Если на некотором шаге делается выбор такой точки, что между нею (выбранной) и ей соотвтетствующим лидером находится несколько точек, то эти точки присоединяются к запаздывающему лидеру последовательно.
Если осталась одна точка или ни одной, то она(они) - замыкающие.
В общем то получается перебор ...


Как-то так, ...

[Dragon65]

Очень сложно всё получается, я пытаюсь задать координаты x и y, при этом иксы заносятся в один массив, игреки в другой, после нужно проанализировать массивы и вычислить точку min/max либо как Виктор сказал Лидирующие точки, так какую из них?


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

Вот ещё поиск максимумов X и Y:

var
    Z: array[1..1000000] of integer;
    K: array[1..1000000] of integer;
    max_index1,max_num1,max_num, max_index:integer;
    i,x,y:integer;
    N:longint;

begin
writeln('Введите количество точек, от 3 до миллиона');
readln(N);
writeln('Введите координаты x,y последовательно всех N точек,после координаты точек записываются в два массива для x и y');
    for i := 1 to N do begin
    read(x,y);
        Z[i]:=x;
        K[i]:=y;
        end;

    max_index := 1;
    max_num := Z[1];

    for i := 2 to N do
        if Z[i] > max_num then begin
            max_index := i;
            max_num := Z[i];
        end;
       max_index1:=1;
       max_num1:= K[1];
       for i := 2 to N do
        if K[i] > max_num1 then begin
            max_index1 := i;
            max_num1 := K[i];
        end;
    writeln;
    writeln ('Максимум X = ',max_num,'Позиция точки: ', max_index);
    writeln ('Максимум Y = ',max_num1,'ПОзиция точки:', max_index1);


end.

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

[Dragon65]

Далее я думаю можно брать разницу между максимальным значением max_num/max_num1 и каким-то членом Z[i] для X и K[i] для Y, только нужно определить какая разница будет минимальной из всего массива, как это сделать подскажите пожалуйста.

[Аватар]

Паскаля нет, консоль в Д7. Для приведенного примера работает, дальше нужно тестить

program Project1;

{$APPTYPE CONSOLE}

uses SysUtils, Math;

type TMyRecord = record
       Corner,Distance: Real;
       NomPP: Longint;
       x,y: Integer;
     end;
var F1,F2: Text;
    i,j,n: Longint;
    a: array[1..1000000] of TMyRecord;
    b: TMyRecord;
    minx,maxx,miny,maxy,x1,y1: Integer;
    x,y: Real;

begin

  {Чтение входных данных}
  Assign(F1,'Input.txt');
  Reset(F1);
  minx:=1001; maxx:=-1001;
  miny:=1001; maxy:=-1001;
  Readln(F1,n);
  for i:=1 to n do begin
    Readln(F1,a[i].x,a[i].y);
    a[i].NomPP:=i;
    if a[i].x<minx then minx:=a[i].x;
    if a[i].x>maxx then maxx:=a[i].x;
    if a[i].y<miny then miny:=a[i].y;
    if a[i].y>maxy then maxy:=a[i].y;
  end;
  Close(F1);

  {Выбор опорной точки}
  x1:=(maxx-minx) div 2;
  y1:=(maxy-miny) div 2;
  x:=minx+x1;
  if x1=0 then x:=x+0.5 else x:=x-0.5;
  y:=miny+y1;
  if y1=0 then y:=y+0.5 else y:=y-0.5;

  {Определение углов и расстояния}
  for i:=1 to n do begin
    a[i].Corner:=ArcTan2(y-a[i].y,x-a[i].x);
    a[i].Distance:=Sqrt(Sqr(x-a[i].x)+Sqr(y-a[i].y));
  end;

  {Сортировка}
  for i:=1 to n-1 do
    for j:=i+1 to n do
      if (a[j].Corner<a[i].Corner) or ((a[j].Corner=a[i].Corner) and (a[j].Distance>a[i].Distance)) then begin
        b:=a[i];
        a[i]:=a[j];
        a[j]:=b;
      end;

  {Результат}
  Assign(F2,'Output.txt');
  Rewrite(F2);
  for i:=1 to n do Write(F2,a[i].NomPP,' ');
  Close(F2);

end.