• Торт для жюри
  PIE
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
K членов жюри X Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах

Задание
Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов


Входные данные
В первой строке входного файла содержатся два целых числа K и N (1≤K,N≤50). Далее следуют N пар вещественных чисел – координаты последовательно расположенных вершин N-угольника

Выходные данные
Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой чисел – координатами своих концов. Все числа должны быть разделены пробелами и/или символами перевода строки


Например:

PIE.IN
4 3
2 1
0 0.5
4 0.5

PIE.OUT
2 1  1 0.5
2 1  2 0.5
2 1  3 0.5





Идеи
Площадь треугольника

Комментарии
Найдем площадь основания куска торта для одного члена жюри. Для этого вычислим общую площадь многоугольника S и разделим ее на количество членов K. Отрезать куски членам жюри будем по очереди: сначала отрежем первому, затем от оставшегося многоугольника отрежем второму и т.д. Все разрезы при этом будем проводить через первую вершину исходного многоугольника.
 
Для отрезания очередного куска поступим следующим образом. Один конец разреза уже фиксирован, а второй перемещается по контуру оставшегося многоугольника до тех пор, пока не "отмерит" нужную площадь. Сначала он перемещается, прыгая от одной вершины многоугольника к следующей (каждый раз при этом к площади ранее отмеренного куска добавляется площадь треугольника, образованного первой, текущей и следующей вершинами). Как только мы отмерим лишнего (т.е. площадь куска, отрезанного через текущую вершину, меньше S/K, а через следующую – больше), в качестве второго конца разреза нужно взять точку на только что пройденной стороне многоугольника. Осталось разделить эту сторону в отношении, приводящем к куску требуемой площади


Упражнение
Решите аналогичную задачу о разрезании для случая невыпуклого торта и K = 2, 3



Решение

{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
 
program pie;
type float = double;
var n1, n, k: integer;
    x, y: array [1..320] of float;
    l, r: integer;
    Sq: float;
    x1, y1, y2: array [1..320] of float;
 
procedure ReadAll;
var i: integer;
begin
  assign (input, 'pie.in');
  reset (input);
    read (k);
    read (n);
    for i := 1 to n do
      read (x[i], y[i]);
  for i := 1 to n do
  begin
    x[i+n] := x[i];
    y[i+n] := y[i];
  end;
  close (input);
end;
 
procedure FindSq;
var i: integer;
begin
  sq := 0;
  for i := 2 to n-1 do
    sq := sq + abs((x[i]-x[1]) * (y[i+1]-y[1]) - (y[i]-y[1]) * (x[i+1]-x[1]));
end;
 
procedure CutSq (s: float);
var ds, ns, cs: float;
    i: integer;
    xx, yy: float;
begin
  i := 1;
  cs := 0;
  while cs < s do
  begin
    inc (i);
    ns := abs((x[i]-x[1]) * (y[i+1]-y[1]) - (y[i]-y[1]) * (x[i+1]-x[1]));
    cs := cs + ns;
  end;
  cs := cs - ns;
  ds := s-cs;
  xx := x[i] + (x[i+1]-x[i]) * ds/ns;
  yy := y[i] + (y[i+1]-y[i]) * ds/ns;
  writeln (x[1]{:10:10},' ',y[1]{:10:10},' ', xx{:10:10},' ',yy{:10:10});
end;
 
procedure Solve;
var i: integer;
begin
  FindSQ;
  assign (output, 'pie.out'); rewrite (output);
  for i := 1 to k-1 do
   CutSq (i / k * abs(Sq));
   close (output);
end;
 
begin
  ReadAll;
  Solve;
end.

 

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