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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 26.01.2019, 17:14   #11
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Правильную организацию цикла перебора точек
А чего только перебор? Там задача полностью решена, осталось вывести только k. Для тех кто не понял - функция scalar проверяет ортогональность отрезков, используя скалярное произведение направляющих векторов )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 26.01.2019, 17:46   #12
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,536
По умолчанию

Ottava - а что это за частный случай ? Дело в том, что мой вариант (не подматривал, бо того ответа еще не было ) совпал с Purpoev (тнлепатия, однако). Все равно, еще допиливать надо для "уборки" дублей и прямоуг. с нулевыми длинами сторон.
Дошло потихоньку, что нулевая длина стороны будет именно у дублей.

Последний раз редактировалось digitalis; 26.01.2019 в 21:05.
digitalis вне форума Ответить с цитированием
Старый 26.01.2019, 17:56   #13
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
А чего только перебор? Там задача полностью решена, осталось вывести только k. Для тех кто не понял - функция scalar проверяет ортогональность отрезков, используя скалярное произведение направляющих векторов )
К "программерскому" подходу вопросов нет, всё сделано грамотно: отдельный цикл перебора и отдельная функция "удовлетворения критериям поиска", которую можно допиливать под нужные условия (ищи хоть трапеции, хоть ромбы).

Проверка ортогональности по 3-м точкам - недостаточное условие. На вскидку мне кажется что она не найдет левый по рисунку и, скорее всего, даст сбой на правом (вопрос будет ли в целых числах красная точка, как я нарисовал).

Надёжнее всего проверять в функции Scalar() какую-нибудь из теорем о прямоугольнике из школьной геометрии, и передавать туда сразу 4 точки.

И надо проверять исходный массив на дубли точек (частные случаи, на которых программа споткнётся, а человек - нет - то о чем отметил digitalis про нулевые размера сторон):
- одна дублированная точка даст прямоугольник, вырожденный в "уголок" типа L
- точка с 4-я дублями даст прямоугольник, "вырожденный в точку".
они тоже могут попасть под условие отсева.


PS: Кстати, проверять "условие ортогональности 3-х точек" - отличная идея для оптимизации отсева третьей точки. Проверять как сумма квадратов катетов = квадрату гипотенузы, чтобы работало на любых углах поворота прямоугольника в системе координат.
Изображения
Тип файла: jpg img1.jpg (44.1 Кб, 57 просмотров)
Тип файла: jpg img2.jpg (43.1 Кб, 99 просмотров)
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 26.01.2019 в 18:04.
Ottava вне форума Ответить с цитированием
Старый 26.01.2019, 18:16   #14
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Там три разных угла четырехугольника проверяется. Попробуй построить четырехуголник с 4-ым не прямым углом, если другие 3 прямые )

ЗЫ - на счет частных случаев - нет ни каких совпадающих точек, которые рисует Сережа. А то начнется - есть совпадающие, или что делать если дробное число ввели, или слово мама вместо числа, или три пары точек вместо минимальных четырех ну и т.п.)
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 26.01.2019 в 18:31.
Аватар вне форума Ответить с цитированием
Старый 26.01.2019, 20:44   #15
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Там три разных угла четырехугольника проверяется. Попробуй построить четырехуголник с 4-ым не прямым углом, если другие 3 прямые )
Я себе полчаса мозг ломал, пока делал реверс-индженеринг формулы из Scalar() обратно в алгоритм. Это тот случай, когда накодить своё проще, чем разобраться в чужом недокументированном коде
Я сходу увидел только проверку 2-х противоположных углов, этого мало - см рисунок внизу. Проверки 3-х углов однозначно достаточно для Евклидовой геометрии.


Цитата:
Сообщение от Аватар Посмотреть сообщение
ЗЫ - на счет частных случаев - нет ни каких совпадающих точек, которые рисует Сережа.
Да, справедливое замечание. При таком подходе совпадающих точек быть не может.

Правда, они могут возникнуть, когда руками вводишь 100 точек в программу. Я бы перестраховался и проверил массив на дубли, жизнь научила меня не доверять пользовательским данным.
Но, согласен, это выходит за рамки поставленного ТЗ.
Изображения
Тип файла: jpg img3.jpg (32.5 Кб, 57 просмотров)
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 26.01.2019 в 21:00.
Ottava вне форума Ответить с цитированием
Старый 26.01.2019, 21:06   #16
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Я сходу увидел только проверку 2-х противоположных углов, этого мало
Код:
function Scalar(p,p1,p2: TMyRecord): Integer;
p - координаты угловой точки
p1,p2 - координаты концов отрезков исходящих из точки p
и три обращения с разными угловыми точками:
Код:
Scalar(m[i],m[j],m[i1])
Scalar(m[i1],m[i],m[j1])
Scalar(m[j],m[i],m[j1])
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 26.01.2019, 21:32   #17
Ottava
Форумчанин
 
Регистрация: 05.09.2017
Сообщений: 157
По умолчанию

Аватар, нет сомнений, что 99% местных форумчан победят в этой олимпиаде.
Я-то хотел провести мастер-класс при вашей поддержке, чтобы топискстартер сам по шагам додумался до решения этой задачи.

Потом - подискутировать есть ли смысл в оптимизации выбора третьей точки - например, проверять образует ли она прямой угол с первыми двумя. Провести эксперимент с замерами времени исполнения.

На примере твоей функции Scalar() можно было бы устроить лёгкий холливар о читабельности кода (я, например, сразу в неё и не въехал, и потом тоже не въехал) при его дальнейшей поддержке

Далее - поднять тему проверки вводимых пользователем данных и граничных условий. Ведь программе пофигу, она может и КПД > 100% насчитать. Всем интеллектом и разумностью поведения программу может наделить только программист.

А в итоге за топикстартера просто решили задачу "коллеги по цеху".
Безопасность с Content Security Policy

Последний раз редактировалось Ottava; 26.01.2019 в 21:37.
Ottava вне форума Ответить с цитированием
Старый 26.01.2019, 21:57   #18
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

А ни чего, ТС грозился разобраться с кодом, заодно, если и правда будет разбираться, немного придется в аналитическую геометрию или в векторную алгебру въехать. Что бы не казалось, что кроме теоремы Пифагора в геометрии и нет ничего )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

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

Вот мой код. И да, можете не искать там ошибки, именно по задаче, если что-то и есть в коде, то оно не мешает правильному условию. К тому же все тесты у меня уже прошли на полный бал.

Код:
#include <iostream>
#include <math.h>
#include <fstream>


using namespace std;
double x[100],y[100];
int n,ans=0,s[6];

int main ()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
	cin >> n;
    for (int i=0;i<n;i++)
    {
       cin >> x[i] >> y[i] ;
    }

    for (int p=0;p<n-3;p++)

         for (int t=p+1;t<n-2;t++)

             for (int i=t+1;i<n-1;i++)

                 for (int j=i+1;j<n;j++)
    {
        s[0] =  pow(x[p]-x[t],2) + pow(y[p]-y[t],2) ;
        s[1] =  pow(x[p]-x[i],2) + pow(y[p]-y[i],2) ;
        s[2] =  pow(x[p]-x[j],2) + pow(y[p]-y[j],2) ;

        s[3] =  pow(x[t]-x[i],2) + pow(y[t]-y[i],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) ;


        if (        (  (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]) ) ) ++ans;


    }

    cout << ans;
	return 0;
}

Цитата:
Правильную организацию цикла перебора точек уже показал Аватар, и там вряд ли придумаешь что-то новое.
А все алгоритмы которые мне здесь и там кидали были с разными недочётами (не знаю какими именно), и не один чётко не выпонялся. Хотя по сути я смотрел, и видел, что по сути ничего нового не было, такие же идеи, как и у меня была. Но не мог понять почему же эти идеи не срабатывали. Ну и,кстати раз Вы были на том форуме, то и код Вы там видели, странно, что просите. И могли заметить, что я писал, что у меня лишь одно лишнее условие было(до того как я писал на форумы, код был таковым+то условие).

Задача была для 7-8 кл (2010 г)

Цитата:
Она не такая уж и простая, как кажется с первого взгляда...
В том-то и дело , так и есть, если разобраться и сосредоточиться. Тут, считай, я просто "упёрся" в то, что именно прямоугольник(не квадрат)! А задача на самом деле лёгкая (на код выше ушло около 15 мин, а остальное время ушло на удаление одного условия ) И всё Вот так вот...
Юрий12 вне форума Ответить с цитированием
Старый 27.01.2019, 01:09   #20
Юрий12
 
Регистрация: 05.04.2017
Сообщений: 8
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Что бы не казалось, что кроме теоремы Пифагора в геометрии и нет ничего )
Эм...я не в 5 классе учусь и достаточно хорошо знаю как геометрию, так и алгебру.
Да и к тому же, я ещё до ваших сообщений последних (да и сюда зашёл,как видите, только сейчас) разобрался с моей проблемой. Уже выше писал, что код у меня (мой) готовый был ещё до сообщений на форумы, и после я убрал лишь одно условие.

Цитата:
Сообщение от digitalis Посмотреть сообщение
совпал с Purpoev
И судя по этим словам, то некоторые уже видели тему на том форуме.

Цитата:
Сообщение от Аватар Посмотреть сообщение
ТС грозился разобраться с кодом, заодно, если и правда будет разбираться
Так что, мне этого не надо уже, благодарю.
А первый код, и единственный, который здесь был до того как решил проблему - это был с функцией Scalar (25.01.2019, 13:16)

Цитата:
Сообщение от Аватар Посмотреть сообщение
осталось вывести только k
И я его тогда сразу проверил, он работал аналогично моему, и не проходил.

Так вот, мне там (на "другом" форуме) и объяснили(а вообще напомнили), то , на что я не обращал внимания.
Юрий12 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 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