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

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

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


Входные данные
В первой строке входного файла записано целое число N - количество деревьев в королевском лесу (2
N14). Деревья нумеруются последовательными целыми числами от 1 до N. Каждая из последующих N строк содержит четыре целых числа хii,vi,li, описывающих очередное дерево. Числа (хi,уi) - это координаты дерева на плоскости, vi - его стоимость, а li - длина забора, который может быть построен из этого дерева. Все числа vi и li, а также абсолютные величины хi и уi - целые числа из диапазона [0,10000]. Считается, что деревья имеют нулевой радиус

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


Например:

FENCE.IN
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8


FENCE.OUT
2 4 5
3.16





Идеи
Перебор с отсечениями, выпуклая оболочка

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

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


 


Решение

{.$define Debug}
 
program fence;
{$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 = 'fence.in';
  outFile = 'fence.out';
{$else}
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V-,X+,Y+}
const
  inFile = 'fence.in';
  outFile = 'con';
  dbgFile = 'con';
var
  dbg: Text;
{$endif}
 
const
  maxN = 14;
  eps = 1e-6;
  inf = maxlongint;
 
type
  int = longint;
  float = extended;
  TBool = array[1..maxN] of boolean;
 
var
  n: integer;
  extra: float;
  answer: TBool;
  x,y,v,l: array[1..maxN] of int;
  dist: array[1..maxN,1..maxN] of float;
  dist2: array[1..maxN,1..maxN] of int;
  bestUse: TBool;
  bestCard: integer;
  bestV: int;
  bestExtra: float;
  use: TBool;
 
function Cardinal(var b : TBool) : integer;
var
  i,j: integer;
begin
  j := 0;
  for i := 1 to n do
    if b[i] then inc(j);
  Cardinal := j;
end;
 
function BuildConvexHull : float;
var
  i,j,k: integer;
  minX,minY: int;
  maxD: int;
  newD: int;
  len: float;
  used: TBool;
  start: integer;
  v: int;
begin
  len := 0;
  minX := inf;
  minY := inf;
  for i := 1 to n do
    if use[i] then
      if (y[i] < minY) or ((y[i] = minY) and (x[i] < minX)) then begin
        minX := x[i];
        minY := y[i];
        j := i;
      end;
 
  fillchar( used, sizeof(used), false );
  used[j] := true;
  start := j;
  i := j;
 
  repeat
 
    maxD := 0;
    k := i;
    for j := 1 to n do
      if use[j] and (not used[j] or (j = start)) then begin
        newD := sqr( x[i] - x[j] ) + sqr( y[i] - y[j] );
        v := (x[j] - x[k]) * (y[i] - y[k]) - (y[j] - y[k]) * (x[i] - x[k]);
        if (v < 0) or ((v = 0) and (newD > maxD)) then begin
          k := j;
          maxD := newD;
        end;
      end;
 
    if k = start then begin
      len := len + dist[i,start];
      BuildConvexHull := len;
      exit;
    end;
 
    len := len + dist[i,k];
    i := k;
    used[k] := true;
 
  until false;
end;
 
procedure Solve;
var
  xx: word;
  i,j: integer;
  curV: int;
  curLen: int;
  curCard: integer;
  curExtra: float;
begin
  for i := 1 to n do
    for j := 1 to n do begin
      dist2[i,j] := sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
      dist[i,j] := sqrt(dist2[i,j]);
    end;
 
  bestV := inf;
  bestCard := maxint;
 
  for xx := 1 to (1 shl n) - 1 do begin
    fillchar(use, sizeof(use), false);
    for i := 1 to n do
      if xx and (1 shl (i-1)) <> 0 then use[i] := true;
    curV := 0;
    for i := 1 to n do
      if not use[i] then inc(curV, v[i]);
    if curV > bestV then continue;
      curCard := Cardinal(use);
    curLen := 0;
    for i := 1 to n do
      if not use[i] then inc(curLen, l[i]);
    curExtra := curLen - BuildConvexHull;
    if curExtra < -eps then continue;
 
    if (curV < bestV) or ((curV = bestV) and (curCard > bestCard)) then begin
      bestUse := use;
      bestV := curV;
      bestExtra := curExtra;
      bestCard := curCard;
    end;
  end;
  answer := bestUse;
  extra := bestExtra;
end;
 
procedure ReadData;
var
  i: integer;
begin
  read(n);
  for i := 1 to n do read(x[i], y[i], v[i], l[i]);
end;
 
procedure WriteData;
var
  i: integer;
begin
  write('Cut these trees:');
  for i := 1 to n do
    if not answer[i] then write(' ', i);
  writeln;
  writeln('Extra wood: ', extra:0:2);
end;
 
procedure Initialize;
begin
  assign(input, inFile);
  reset(input);
  assign(output, outFile);
  rewrite(output);
 
  {$ifdef Debug}
  assign( dbg, dbgFile );
  rewrite(dbg);
  writeln('----Initialized----');
  {$endif}
end;
 
procedure Finalize;
begin
  {$ifdef Debug}
  close(dbg);
  writeln('----Finalized----');
  {$endif}
  close(input);
  close(output);
  halt(0);
end;
 
begin
  Initialize;
  ReadData;
  Solve;
  WriteData;
  Finalize;
end.




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