Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.11.2011, 10:54   #1
ubun
Форумчанин
 
Аватар для ubun
 
Регистрация: 06.12.2010
Сообщений: 198
По умолчанию задача на прямоугольники

Покажите пожалуйста решение данной задачи (плиз!)
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 вне форума Ответить с цитированием
Старый 30.11.2011, 10:56   #2
ubun
Форумчанин
 
Аватар для ubun
 
Регистрация: 06.12.2010
Сообщений: 198
По умолчанию

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

000444
11133

Пример output.txt

1.000 2.000 3.000 2.000
ubun вне форума Ответить с цитированием
Старый 30.11.2011, 12:26   #3
Mandrivnyk
Software Developer
Участник клуба
 
Аватар для Mandrivnyk
 
Регистрация: 01.03.2011
Сообщений: 1,098
По умолчанию

Цитата:
Х[ и Х2 и У2, Х'ъ и Уз
Я, как бы понимаю, что имеется в виду X1 и Y1, X2 и Y2, X3 и Y3, но несколько коробит отсутствие внимания при создании поста...
В конце-концов, кому надо решение? Тебе или людям, у которых ты просишь помощи? -)
Далее.
Цитата:
Во второй строке — три пары чисел
Цитата:
11133
Вот хоть убей -- три пары чисел тут нету.

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

И потом -- ты просишь готовое решение? Тогда тебе во фриланс -- бесплатно вряд ли кто-то сделает.
Хочешь, чтобы _помогли_ -- сделай хотя бы что-то сам. Например, опиши алгоритм решения.
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв.
Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062
Mandrivnyk вне форума Ответить с цитированием
Старый 30.11.2011, 14:08   #4
alex77755
Форумчанин
 
Аватар для alex77755
 
Регистрация: 14.02.2009
Сообщений: 753
По умолчанию

Тут математики больше чем программирования. Выведи формулу рассчёта и выложи, а применить её в программе не составить труда. Можно, конечно в цикле перебирать варианты. Но 0; 10^9 с точностью не менее 3 знаков после запятой займеёт немало времени
помогу решить контрольные VB6, VBA (недорого)
Alex77755@mail.ru
alex77755 вне форума Ответить с цитированием
Старый 30.11.2011, 16:22   #5
alex77755
Форумчанин
 
Аватар для alex77755
 
Регистрация: 14.02.2009
Сообщений: 753
По умолчанию

Вариант ускорения - метод деления отрезка пополам
помогу решить контрольные VB6, VBA (недорого)
Alex77755@mail.ru
alex77755 вне форума Ответить с цитированием
Старый 30.11.2011, 20:37   #6
ubun
Форумчанин
 
Аватар для ubun
 
Регистрация: 06.12.2010
Сообщений: 198
По умолчанию

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

правильно так 111333
ubun вне форума Ответить с цитированием
Старый 30.11.2011, 22:33   #7
val_nnm
Форумчанин
 
Регистрация: 18.10.2009
Сообщений: 185
По умолчанию

Обший план матиматического решения:
Вообще существует бесконечное множество решений. (причем решения существуют всегда) Единственно за отсутвсие решения можно считать ситуацию если площадь внешнего прямоугольника = 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 точек сделайте перемещение и поворот обратные сделанному вначале.
И получившиеся точки и будут решением.
Изображения
Тип файла: jpg p120.jpg (34.4 Кб, 127 просмотров)
На С# пишу лучше чем на русском.
"У меня правильнописание хромает. Оно хорошее, но почему-то хромает."
val_nnm вне форума Ответить с цитированием
Старый 01.12.2011, 10:41   #8
ubun
Форумчанин
 
Аватар для ubun
 
Регистрация: 06.12.2010
Сообщений: 198
По умолчанию

Я тоже так рассуждал. Но про повернутый прямоугольник пропустил
Я думаю решать надо просто так
1. Найти четвертые координаты
2. взять от одной из сторон на расстоянии h (внутри прямоугольника) параллельный отрезок.
3. Проверка что отрезок не касается внутренного прямоугольника и не пересекает его
4. вычислить площади справа и слева, и проверить на точность разности этих площадей eps<0,001
5. если отрезок касается или пересекает внутрений прямоугольник то также вычислить его площади справа и слева потом отделить их от площадей правого и левого большого прямоугольника.
6 . и тд двигая отрезок впрво и влево в зависимости от знака разности, а h изменяется от точности h=h/2
ubun вне форума Ответить с цитированием
Старый 01.12.2011, 23:05   #9
ubun
Форумчанин
 
Аватар для ubun
 
Регистрация: 06.12.2010
Сообщений: 198
По умолчанию

у меня работает только при симметричном виде, в чем ошибка
Код:
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.
ubun вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программой на СИ++. Прямоугольники KOMPNET Помощь студентам 11 13.10.2011 19:03
как реализовать чтобы при нажатии прямоугольники меняли цвета не зависимо друг от друга programmm Win Api 0 18.05.2011 17:50
Линии или прямоугольники на NASM, assembler Lexeres Помощь студентам 0 26.03.2011 11:25
Алгоритм разбиения двухмерной сетки ячеек на выпуклые прямоугольники(язык не важен) Qmaks Помощь студентам 0 17.10.2010 14:07
прямоугольники C++ Studentka_:) Помощь студентам 4 17.03.2010 10:13