• Шагающий многоугольник
  MOVESEQ
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
На плоскости заданы выпуклый многоугольник M и точка P(x,y). За один ход разрешается центрально-симметрично отразить многоугольник относительно середины любой из его сторон

Задание
Требуется определить последовательность ходов, в результате которой точка P оказалась бы накрытой этим многоугольником


Входные данные
Во входном файле записано количество вершин многоугольника N (3≤N≤20) и координаты точки x и y. Далее перечислены координаты вершин многоугольника в порядке обхода по часовой стрелке. Все координаты - целые числа, не превосходящие по абсолютной величине 10⁵

Выходные данные
Если точку P накрыть нельзя, запишите в выходной файл сообщение "Impossible". В противном случае выведите в него последовательность ходов, после выполнения которой многоугольник M накроет точку P. Каждый ход задается номерами вершин той стороны, относительно середины которой производится преобразование центральной симметрии. Вершины многоугольника нумеруются начиная с 1


Например:

MOVESEQ.IN
3 3 2
0 1  1 2  1 0

MOVESEQ.OUT
2 3
3 1
2 3





Комментарии
Выполнение двух "шагов" многоугольника M относительно середин двух различных его сторон приводит к параллельному переносу M на удвоенный вектор, соединяющий середины этих сторон. Взяв, например, первые три стороны многоугольника M, мы получим два неколлинеарных вектора сдвига. Параллельными переносами M вдоль этих векторов можно достаточно близко приблизить его к точке P. Далее нужно устроить перебор, то есть последовательно проделывать "шаги" относительно одной, двух и т.д. сторон M и проверять, принадлежит ли точка полученному многоугольнику или нет

Можно доказать, что точку всегда можно накрыть, поэтому и описанный алгоритм ответ находит всегда. Заметим, что можно считать многоугольник M неподвижным, а точку P при каждом "шаге" отображать центрально-симметрично. Это ускоряет работу программы





Решение

{.$define Debug}
program moveseq;
{$M 16384,0,655360}
 
{$ifndef Debug}
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X+,Y+}
const
  inFile = 'moveseq.in';
  outFile = 'moveseq.out';
{$else}
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V-,X+,Y+}
const
  inFile = 'moveseq.in';
  outFile = 'con';
  dbgFile = 'con';
var
  dbg: Text;
{$endif}
 
const
  maxN = 21;
  maxT = 170;
  maxDepth = 20;
  msgImpossible = 'IMPOSSIBLE';
  srcDepth = 5;
type
  int = longint;
var
  n : integer;
  x,y : array[1..maxN] of int;
  x0,y0 : int;
  timer : longint absolute 0:$46c;
  startTime  : longint;
  endTime : longint;
  src : array[1..maxDepth] of integer;
  minD,maxD : comp;
  buf : pointer;
  inf : comp;
 
procedure Finalize; forward;
 
procedure Impossible;
begin
  {$ifndef Debug}
  close( output );
  erase( output );
  assign( output, outFile );
  rewrite( output );
  {$endif}
  writeln( msgImpossible );
  Finalize;
end;
 
procedure Apply( k : integer );
var
  xx,yy : int;
  i : integer;
begin
  xx := (x[k] + x[k+1]) div 2;
  yy := (y[k] + y[k+1]) div 2;
  for i := 1 to n + 1 do begin
    x[i] := - x[i] + xx * 2;
    y[i] := - y[i] + yy * 2;
  end;
end;
 
function min( a, b : int ) : int;
begin
  if a < b then min := a else min := b;
end;
 
function max( a, b : int ) : int;
begin
  if a < b then max := b else max := a;
end;
 
function IsInside : boolean;
var
  i,j : integer;
  x1,x2,y1,y2 : int;
  w : boolean;
begin
  j := 0;
  IsInside := true;
  for i := 1 to n do begin
    x1 := min( x[i], x[i+1] );
    y1 := min( y[i], y[i+1] );
    x2 := max( x[i], x[i+1] );
    y2 := max( y[i], y[i+1] );
    if (x0 = x[i]) and (y0 = y[i]) then exit;
    if (x0 >= x1) and (x0 <= x2) and
       (y0 >= y1) and (y0 <= y2) and
       ((x0 - x[i]) * (y[i+1] - y[i]) = (y0 - y[i]) * (x[i+1] - x[i])) then exit;
  end;
  IsInside := false;
  j := 0;
  for i := 1 to n do begin
    if y[i] = y[i+1] then continue;
    if y[i] < y[i+1] then begin
      x1 := x[i];
      y1 := y[i];
      x2 := x[i+1];
      y2 := y[i+1];
    end else begin
      x2 := x[i];
      y2 := y[i];
      x1 := x[i+1];
      y1 := y[i+1];
    end;
    if (y0 >= y1) and (y0 < y2) then begin
      if x1 = x2 then begin
        if x0 < x1 then inc( j );
      end else begin
        if (y0 - y1) * (x2 - x1) / (y2 - y1) + x1 > x0 then inc( j );
      end;
    end;
  end;
  IsInside := odd( j );
end;
 
procedure Search( depth : integer );
var
  i : integer;
begin
  if depth > srcDepth then exit;
  if timer > endTime then Impossible;
  for i := 1 to n do begin
    Apply( i );
    src[depth] := i;
    if IsInside then begin
      for i := 1 to depth do
        if src[i] < n then
          writeln( src[i], ' ', src[i] + 1 )
        else
          writeln( n, ' ', 1 );
      Finalize;
    end;
    Search( depth + 1 );
    Apply( i );
  end;
end;
 
procedure Dist;
var
  i : integer;
  d : comp;
  a,b : comp;
begin
  minD := inf;
  maxD := 0;
  if IsInside then begin
    minD := 0;
    maxD := 0;
    exit;
  end;
  for i := 1 to n do begin
    a := x0 - x[i];
    b := y0 - y[i];
    d := sqr( a ) + sqr( b );
    if d > maxD then maxD := d;
    if d < minD then minD := d;
  end;
end;
 
procedure Solve;
var
  prevMin : comp;
  prevMax : comp;
  newD : comp;
  min : comp;
  max : comp;
  i,j : integer;
begin
  Dist;
  prevMin := minD;
  prevMax := maxD;
  repeat
    if IsInside then Finalize;
    min := inf;
    max := 0;
    for i := 1 to n do begin
      Apply( i );
      Dist;
      if (minD = min) and (maxD < max) then begin
        max := maxD;
        j := i;
      end;
      if minD < min then begin
        min := minD;
        max := maxD;
        j := i;
      end;
      Apply( i );
    end;
    if (min > prevMin) or
       (min = prevMin) and (max > prevMax) then break;
    if j < n then
      writeln( j, ' ', j + 1 )
    else
      writeln( n, ' ', 1 );
    Apply( j );
    prevMin := min;
    prevMax := max;
  until false;
  if IsInside then Finalize;
  Search( 1 );
  Impossible;
end;
 
procedure ReadData;
var
  i : integer;
begin
  read( n, x0, y0 );
  x0 := x0 * 2;
  y0 := y0 * 2;
  for i := 1 to n do begin
    read( x[i], y[i] );
    x[i] := x[i] * 2;
    y[i] := y[i] * 2;
  end;
  x[n+1] := x[1];
  y[n+1] := y[1];
end;
 
procedure Initialize;
begin
  assign( input, inFile );
  reset( input );
  assign( output, outFile );
  rewrite( output );
 
  {$ifdef Debug}
  assign( dbg, dbgFile );
  rewrite( dbg );
  writeln( '----Initialized----' );
  {$endif}
 
  startTime := timer;
  endTime := startTime + maxT;
  inf := 1e17;
 
  {$ifndef Debug}
  getmem( buf, 32768 );
  settextbuf( output, buf^, 32768 );
  {$endif}
end;
 
procedure Finalize;
begin
  {$ifdef Debug}
  close( dbg );
  writeln( '----Finalized----' );
  {$endif}
 
  close( input );
  close( output );
  halt( 0 );
end;
 
begin
  Initialize;
  ReadData;
  Solve;
  Finalize;
end.

 

© Особенности национальных задач по информатике