задача на прямоугольники

[ubun]

Покажите пожалуйста решение данной задачи (плиз!)
2. Два прямоугольника

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

Формат входного файла input.txt

Входной файл состоит из двух строк. В первой строке записаны три пары чисел Хги Уи Х2 и У2, Х3 и У3, задающих координаты вершин большего прямоугольника в порядке обхода по часовой стрелке. Во второй строке — три пары чисел Х[ и Х2 и У2, Х'ъ и Уз, задающих координаты вершин прямоугольного отверстия впорядке обхода по часовой стрелке. Все числа целые в диапазоне [0; 10^9 ].

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

Формат выходного файла output.txt:

В выходном файле записаны две пары положительных чисел — координаты любых двух различных точек прямолинейного разреза, делящего площадь пластины на две равновеликие части. Все эти числа разделены пробелом и находятся в диапазоне [0; 10^9 ]. Если возможных решений несколько, выведите любое из них с точностью не менее 3 знаков после запятой. Выходной файл должен содержать слово N0, если задача не имеет решения.
Пример input.txt Пример output.txt
000444 11133 1.000 2.000 3.000 2.000

[ubun]

точнее так
Пример input.txt

000444
11133

Пример output.txt

1.000 2.000 3.000 2.000

[Mandrivnyk]

Х[ и Х2 и У2, Х'ъ и Уз

Я, как бы понимаю, что имеется в виду X1 и Y1, X2 и Y2, X3 и Y3, но несколько коробит отсутствие внимания при создании поста...
В конце-концов, кому надо решение? Тебе или людям, у которых ты просишь помощи? -)
Далее.

Во второй строке — три пары чисел

11133

Вот хоть убей -- три пары чисел тут нету.

Я уже не говорю о том, что не указан даже язык программирования...

И потом -- ты просишь готовое решение? Тогда тебе во фриланс -- бесплатно вряд ли кто-то сделает.
Хочешь, чтобы _помогли_ -- сделай хотя бы что-то сам. Например, опиши алгоритм решения.

[alex77755]

Тут математики больше чем программирования. Выведи формулу рассчёта и выложи, а применить её в программе не составить труда. Можно, конечно в цикле перебирать варианты. Но 0; 10^9 с точностью не менее 3 знаков после запятой займеёт немало времени

[alex77755]

Вариант ускорения - метод деления отрезка пополам

[ubun]

это X1 и Y1, X2 и Y2, X3 и Y3,

правильно так 111333

[val_nnm]

Обший план матиматического решения:
Вообще существует бесконечное множество решений. (причем решения существуют всегда) Единственно за отсутвсие решения можно считать ситуацию если площадь внешнего прямоугольника = 0. (но строго говоря в этм случае - решением являеться абсолюно любая прямая)

Для простоты расчётов будем выбирать линию параллельную одной из сторон внешнего прямоугольника.
Я набрасал небольшой рисунок поясняющий обьяснения. (рисунок неточный, и показывает только общие принципы)

Чтобы упростить матиматику нужно повернуть и переместить прямоугольники таким образом чтобы 2 стороны внешнего прямоугольника совпали с осями X и Y.
Дальше найдите точки A,B,C,D,E,F (с.м. рисунок) (чтобы точки ишли по порядку, отсортируйте кординаты вершин по кординате X)

Дальше нужно построить функцию разности площадей (разность площади находящийся слева и справа от заданной линии перпендекулярной X) для каждого прямоугольника.
разность площадей = площадь слева от линии * 2 - площадь всего прямоугольника
На рисунке площадь слева от линии для большого и маленького прамоугольников нарисованны коричневым и тёмно зелёным.
Графики разностей площадей на графике нарисованны ярко зелёным и ярко красным.
График расзности площадей для большого прямоугольника будет иметь вид kx+b (т.е. прямая линия)

А график разности для маленького прямоугольника будет
на участках AB, EF равен константе.
на участке СВ будет линеен.
На участках BC, DE (если я неошибаюсь) будет полиномом второй степени (иметь форму параболы)

Для вычисления на учатках BC, CB и DE вычислите в точках B, C и D соответсвенно и к ним прибавляйте уравнения.

Дальше нужно найти разность графиков разности площадей (извеняюсь за каламбур) (на рисунке нарисованн желтым)
Можно сказать что этот график будет монотонным.
Дальше нужно найти точку где эта разность будет равна 0.
(для этого ужно сначала найти значения в точках A, B, C, D, E, F. Затем найти тот участок где функция меняет знак, у а затем внутри этого участка аналитически искать точку =0)
Собсвенно эти точка и будет определять кординаты X1 и X2 искомую линию. Кординаты Y1 и Y2 найдите из сторон внешнего прямоугольники.
Дальше для 2 точек сделайте перемещение и поворот обратные сделанному вначале.
И получившиеся точки и будут решением.

[ubun]

Я тоже так рассуждал. Но про повернутый прямоугольник пропустил
Я думаю решать надо просто так
1. Найти четвертые координаты
2. взять от одной из сторон на расстоянии h (внутри прямоугольника) параллельный отрезок.
3. Проверка что отрезок не касается внутренного прямоугольника и не пересекает его
4. вычислить площади справа и слева, и проверить на точность разности этих площадей eps<0,001
5. если отрезок касается или пересекает внутрений прямоугольник то также вычислить его площади справа и слева потом отделить их от площадей правого и левого большого прямоугольника.
6 . и тд двигая отрезок впрво и влево в зависимости от знака разности, а h изменяется от точности h=h/2

[ubun]

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

program pr2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
  var x1,y1,x2,y2,x3,y3,xx1,yy1,xx2,yy2,xx3,yy3,c,a,b,a1,b1,s1,s2,ss1,ss2,dels1,dels2,x4:real;
  label metka;

begin
  readln(x1,y1,x2,y2,x3,y3,xx1,yy1,xx2,yy2,xx3,yy3) ;
  a:=abs(abs(y2)-abs(y1));
  b:=abs(abs(x3)-abs(x1));
  a1:=abs(abs(yy2)-abs(yy1));
  b1:=abs(abs(xx3)-abs(xx1));
  x4:=x3;
  metka:
  begin
  c:=(x3-x2)/2;
  x2:=x1; x3:=x4;
  if (c>xx2) and (c<xx3) then
     begin
     s1:=a*(c-x2); s2:=a*(x3-c);
     ss1:=a1*(c-xx2); ss2:=a1*(xx3-c);
     dels1:=s1-ss1; dels2:=s2-ss2;
     end
     else
  if (c>=xx3) then
     begin
     s1:=a*(c-x2); s2:=a*(x3-c);
     ss1:=a1*b1; ss2:=0;
     dels1:=s1-ss1; dels2:=s2-ss2;
     end
  else
  if (c<=xx2) then
     begin
     s1:=a*(c-x2); s2:=a*(x3-c);
     ss1:=0; ss2:=a1*b1;
     dels1:=s1-ss1; dels2:=s2-ss2;
     end;
     end;
  if (abs(dels1-dels2))<=0.001 then write(c,'/',y1,'/',c,'/',y2,'/',dels1,'/',dels2,'/',a,'/',b,'/',a1,'/',b1)
  else
  if dels1>dels2 then
     begin
     x2:=x2;
     x3:=c;
     goto metka;
     end
  else
  if dels1<dels2 then
     begin
     x2:=c;
     x3:=x3;
     goto metka;
     end;
 readln;
end.