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

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

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 27.01.2019, 23:23   #21
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию

Цитата:
Сообщение от Юрий12 Посмотреть сообщение
Вот мой код. И да, можете не искать там ошибки, именно по задаче, если что-то и есть в коде, то оно не мешает правильному условию. К тому же все тесты у меня уже прошли на полный бал.
Да, я уже понял, что ваша цель - сдать задание, а не разобраться в тонкостях "профессии". Но, большое вам спасибо за предоставленный листинг.

Мой препод сразу закидал бы меня тапками за кучу лишних вычислений во внутреннем цикле. Оптимальный код выглядит так (прошу прощения за С-ишную нотацию фигурных скобок):
Код:
    for (int p=0;p<n-3;p++)
         for (int t=p+1;t<n-2;t++) {
             s[0] =  pow(x[p]-x[t],2) + pow(y[p]-y[t],2) ;
             for (int i=t+1;i<n-1;i++) {
                 s[1] =  pow(x[p]-x[i],2) + pow(y[p]-y[i],2) ;
                 s[3] =  pow(x[t]-x[i],2) + pow(y[t]-y[i],2) ;
                 for (int j=i+1;j<n;j++) {
                     s[2] =  pow(x[p]-x[j],2) + pow(y[p]-y[j],2) ;
                     s[4] =  pow(x[t]-x[j],2) + pow(y[t]-y[j],2) ;
                     s[5] =  pow(x[i]-x[j],2) + pow(y[i]-y[j],2) ;
                      . . .
                     }
                }
           }
Если оптимизация вычисление большой "рояли не играет", программист вынесет "туманные" вычисления в отдельную функцию, как сделал Аватар. В этой функции уже можно тестировать любые алгоритмы проверок на "прямоугольность".

Но самое интересное - в вашем условии 'прямоугольника':
Код:
( ( (s[0]==s[5]) && (s[1]==s[4]) && (s[3]==s[2]) && (s[0]!=s[3]) && (s[1]!=s[3]) ) ||
  ( (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]) && (s[0]!=s[1]) && (s[2]!=s[1]) ) ||
  ( (s[1]==s[4]) && (s[2]==s[3]) && (s[0]==s[5]) && (s[0]!=s[1]) && (s[2]!=s[0]) ) );
Если просто упорядочить вашу запись, видно, что в условии есть общая часть: (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]):
Код:
( ( (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]) && (s[0]!=s[3]) && (s[1]!=s[3]) )  ||
  ( (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]) && (s[0]!=s[1]) && (s[2]!=s[1]) )  ||
  ( (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]) && (s[0]!=s[1]) && (s[2]!=s[0]) ) )
это и есть проверка равенства противоположных сторон и равенства диагоналей. Выносим это условие "за скобки":
Код:
( (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]) // Проверка равенства противоаоложных сторон и равенства диагоналей
  &&    // и какая-то непонятная проверка
     ( ( (s[0]!=s[3]) && (s[1]!=s[3]) ) ||
       ( (s[0]!=s[1]) && (s[2]!=s[1]) ) ||
       ( (s[0]!=s[1]) && (s[2]!=s[0]) ) )
)
Возникло ощущение, что эта "какая-то непонятная проверка" - лишняя. При любом порядке чередования точек p-t-i-j (а их всего 3 разных, остальные - их отражения), проверка s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4] всегда проверяет равенство противоположных сторон и равенство диагоналей. Даже для "невыпуклого" четырёхугольника, см рисунок ниже.
Так и не осилив сакрального смысла этой "непонятной проверки", я тупо убрал её. Паскаля/C++ под руками нет, но вот рабочий код на PHP (инициация массивов опущена), и визуализация решения, для верификации кода:
Код:
$n = count($x);
$ans = array();
for ($p=0; $p<$n-3; $p++)
  for ($t=$p+1; $t<$n-2; $t++)
	for ($i=$t+1; $i<$n-1; $i++)
	  for ($j=$i+1; $j<$n; $j++) {
		$res = isRectangle($x, $y, $p, $t, $i, $j);
		if ($res)  $ans[] = array($p, $t, $i, $j);		// Сохраняем прямоугольник, мы же зачем-то его искали...
		echo Plot($x, $y, array($p, $t, $i, $j), $res, "p=$p, t=$t, i=$i, j=$j");	// Visualisation
		}
echo count($ans);


function isRectangle($x, $y, $p, $t, $i, $j) {
  $s[0] = pow($x[$p]-$x[$t],2) + pow($y[$p]-$y[$t],2);	// Квадрат длины отрезка p-t
  $s[1] = pow($x[$p]-$x[$i],2) + pow($y[$p]-$y[$i],2);	// Квадрат длины отрезка p-i
  $s[2] = pow($x[$p]-$x[$j],2) + pow($y[$p]-$y[$j],2);	// Квадрат длины отрезка p-j
  $s[3] = pow($x[$t]-$x[$i],2) + pow($y[$t]-$y[$i],2);	// Квадрат длины отрезка t-i
  $s[4] = pow($x[$t]-$x[$j],2) + pow($y[$t]-$y[$j],2);	// Квадрат длины отрезка t-j
  $s[5] = pow($x[$i]-$x[$j],2) + pow($y[$i]-$y[$j],2);	// Квадрат длины отрезка i-j

  return ( ($s[0]==$s[5]) && ($s[2]==$s[3]) && ($s[1]==$s[4]) );	// Равны между собой диагонали и противоположные стороны
  }


function Plot($x, $y, $set, $res, $title='') {			// Построить график
  return "<li><img src='/graph.php?y=".implode(',', $y).'&x='.implode(',', $x).'&set='.implode(',', $set)
     .'&title='.urlencode($title)."' class='".($res  ?'bingo'  :'fail')."'></li>";
  }
Sorry за "многобукв", здравая критика приветствуется.
Изображения
Тип файла: jpg variants.jpg (30.3 Кб, 67 просмотров)
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 27.01.2019 в 23:29.
Ottava вне форума Ответить с цитированием
Старый 27.01.2019, 23:50   #22
Юрий12
 
Регистрация: 05.04.2017
Сообщений: 8
По умолчанию

Цитата:
Если просто упорядочить вашу запись, видно, что в условии есть общая часть: (s[0]==s[5]) && (s[2]==s[3]) && (s[1]==s[4]):
Да, я это тоже это заметил, когда писал код.

Цитата:
Возникло ощущение, что эта "какая-то непонятная проверка" - лишняя.
И подумал так же.
Странно, но когда я убрал лишнее и оставил общую часть, то почем-то ответ выдавало не тот.

Но вот сейчас, я снова убрал лишнее, проверил, а сейчас работает. Скорее всего, тогда не то убрал. (а этим условием я "проверял", чтобы диагонали не были равны сторонам, ведь у квадраты и прямоугольника такое невозможно, но затем понял, что это глупо и оно лишне,но вот что-то не то сделал)
Так что да, это лишнее, Вы правы
Юрий12 вне форума Ответить с цитированием
Старый 28.01.2019, 10:04   #23
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
И я его тогда сразу проверил, он работал аналогично моему, и не проходил.
Угу, там не учтен порядок обхода вершин, каюсь. Можно например добавить еще функцию вычисления квадрата расстояния
Код:
function Distance(p1,p2: TMyRecord): Integer;
begin
  Distance:=(p1.X-p2.X)*(p1.X-p2.X)+(p1.Y-p2.Y)*(p1.Y-p2.Y);
end;
и с учетом порядка, исключая самопересечение, сделать что-то в этом роде
Код:
  k:=0;
  for i:=1 to n-3 do
    for j:=i+1 to n-2 do begin
      r1:=Distance(m[i],m[j]);
      for i1:=j+1 to n-1 do begin
        r2:=Distance(m[i],m[i1]);
        for j1:=i1+1 to n do begin
          r3:=Distance(m[i],m[j1]);
          if (r1>r2) and (r1>r3) then begin k1:=i1; k2:=j; k3:=j1; end
          else if (r2>r1) and (r2>r3) then begin k1:=j; k2:=i1; k3:=j1; end
          else begin k1:=j; k2:=j1; k3:=i1; end;
          if (Scalar(m[k1],m[i],m[k2])=0) and
             (Scalar(m[k2],m[k1],m[k3])=0) and
             (Scalar(m[k3],m[k2],m[i])=0) then begin Inc(k); Break; end;
        end;
      end;
    end;
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 28.01.2019, 16:19   #24
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию

Цитата:
Сообщение от Юрий12 Посмотреть сообщение
Скорее всего, тогда не то убрал. (а этим условием я "проверял", чтобы диагонали не были равны сторонам, ведь у квадраты и прямоугольника такое невозможно, но затем понял, что это глупо и оно лишне,но вот что-то не то сделал)
Юрий, поздравляю! Теперь вы не только решили задачу, но и получили оптимально "вылизанный" код программы, за каждую строчку которой можете "набить морду" любому сомневающемуся в ней.

Амбиции у вас есть, желание "докопаться до истины" - есть, умение находить общий язык с другими "амбициозными программистами" - тоже есть. Нам растёт достойная замена, пора думать о пенсии


Цитата:
Сообщение от Аватар Посмотреть сообщение
Угу, там не учтен порядок обхода вершин
Я тоже сначала стал решать задачу проверкой на прямые углы(все остальные школьные теоремы по геометрии я давно забыл), и упёрся в "непонятки" с порядком вершин. Даже функцию упорядочивания вершин многоугольника написал (точнее, перевёл с Python на PHP):
Код:
function order(&$X, &$Y) {						// Упорядость точки многоугольника по часовой стрелке, чтобы правильно нарисовать его (https://stackoverrun.com/ru/q/3764170)
  $cX = array_sum($X)/count($X);					// "центр масс" по X - среднее арифметическое по X
  $cY = array_sum($Y)/count($Y);					// "центр масс" по Y - среднее арифметическое по Y
  foreach ($X as $i => $val)  $fi[$i] = atan2($Y[$i] - $cY, $X[$i] - $cX);// Массив полярных углов точек относительно "центра масс"
  array_multisort($fi, $X, $Y, SORT_ASC, SORT_NUMERIC);			// Сортируем $fi по возрастанию(SORT_ASC) как числа(SORT_NUMERIC), одновременно переставляя $X, $Y
  }
Но это решение задачи в общем виде, для любых фигур. Оно не для олимпиады, где всё легко решается в целых числах.
Кстати, преподу, составившему эту задачу - зачёт. Задачка красивая, ничего лишнего, и есть определённая свобода для творчества в плане поиска оптимального и простого алгоритма "прямоугольности".
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 28.01.2019 в 16:41.
Ottava вне форума Ответить с цитированием
Старый 29.01.2019, 16:06   #25
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию Вишенка на торте или нет предела совершенству

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

Нашему торту явно не хватает "вишенки", и вот она - свежий топик Прямоугольный треугольник, где предложено простое решение определения "прямоугольности" треугольника. А у нас даже квадраты отрезков уже посчитаны, грех не использовать это.

Итак, функция
Код:
function is90(a2, b2, c2) {  // Проверяет, что прямоугольность треугольника с квадратами сторон a2,b2,c2
  return ( (a2 + b2 == c2) || (a2 + c2 == b2) || b2 + c2 == a2) );
  }
Вставляем её в третий цикл:
Код:
for (int p=0;p<n-3;p++)
    for (int t=p+1;t<n-2;t++) {
        s[0] =  pow(x[p]-x[t],2) + pow(y[p]-y[t],2);
        for (int i=t+1;i<n-1;i++) {
            s[1] =  pow(x[p]-x[i],2) + pow(y[p]-y[i],2);
            s[3] =  pow(x[t]-x[i],2) + pow(y[t]-y[i],2);
            if (!is90(s[0], s[1], s[3]))  continue;  // Три точки не образуют прямой угол
            for (int j=i+1;j<n;j++) {
                s[2] =  pow(x[p]-x[j],2) + pow(y[p]-y[j],2);
                s[4] =  pow(x[t]-x[j],2) + pow(y[t]-y[j],2);
                s[5] =  pow(x[i]-x[j],2) + pow(y[i]-y[j],2);
                . . .
                }
            }
        }
и на 25%(грубо) оптимизируем количество ненужных вычислений. Если третья точка не образует прямой угол с первыми двумя - четвёртую точку проверять на "прямоугольник" бессмысленно, и четвёртый цикл можно пропустить.
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 29.01.2019 в 16:18.
Ottava вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Олимпиадная задача lulia Паскаль, Turbo Pascal, PascalABC.NET 3 02.12.2017 11:20
олимпиадная задача danzel1 Общие вопросы C/C++ 2 21.10.2011 15:15
Олимпиадная задача Alexey_kor Помощь студентам 7 30.01.2011 02:22
Олимпиадная задача. _-Re@l-_ Паскаль, Turbo Pascal, PascalABC.NET 1 09.12.2010 20:53
Олимпиадная задача Carbon Общие вопросы C/C++ 2 23.05.2007 22:07