ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Egorov Pavel                         2:5080/169.35  14 Jul 2001  00:38:56
 To : Serge Kanilo
 Subject : Отрезки
 -------------------------------------------------------------------------------- 
 

 
 On Friday July 13 2001 you wrote to All:
 
  >> А я вот умею решать такую задачку СОВСЕМ без частных случаев!
 
  >> Function Cross(xa,ya,xb,yb,xc,yc,xd,yd : Real) : Boolean;
 
  >> Function Check(xa,ya,xb,yb,xc,yc,xd,yd : Real) : Boolean;
  >> begin
  >> xb:=xb-xa;
  >> xc:=xc-xa;
  >> xd:=xd-xa;
  >> yb:=yb-ya;
  >> yc:=yc-ya;
  >> yd:=yd-ya;
  >> Check:=
  >> ((xc*yb-xb*yc>=0) and (xb*yd-xd*yb>=0) and (xc*yd-xd*yc>=0)) or
  >> ((xc*yb-xb*yc<0)  and (xb*yd-xd*yb<0)  and (xc*yd-xd*yc<0))
  >> end;{Check}
 
 Такс, закралась таки подлая... Все '>=' следует заменить на '>'
 Тогда твой пример заработает.
 
  SK> Это наверное шутка?
 
 Hа самом деле да, типа того. Дело было так: Пришлось мне это вбить как-то раз в 
 лоб. Вбил. Hе понравилось мне (Убил более получаса). После этого было решено
 придумать че-нить побыстрее (в смысле написания). По-моему очень даже
 получилось.
 
  SK> Кто будет использовать программу с 24 умножениями (не считая
  SK> всего остального), для того что, если написать в лоб, может
  SK> максимально потребовать 20 сравнений и 4 перестановки?
 
 БЕССПОРHО! это даааааалеко не самый быстрый(в смысле выполнения) вариант.
 А по поводу кто использовать будет - я тебе скажу кто! БЫВАЮТ СЛУЧАИ когда время
 выполнения не критично (побарабану будет оно 0.001сек выполняться или 0.01сек), 
 а время написания критично. Это я клоню ко всяческим олимпиадам, турнирам и тп и
 тд на время (АСМ тот же). Вот собственно именно для этого эта алгоритма и
 придумалась.
 
  >> Если кто не понял как работает - не судьба (шутка :) спрашивайте -
  >> вспомню
 
  SK> И потом еще вспоминать, как и почему это работает :)
 
 Ээээх, заставили таки вспомнить!!!! Потребовалось целых 15 секунд (В 35 раз
 меньше, чем на то, чтобы написать этот ответ... :)
 
  SK> Да и для интервалов стянутых в отрезки программа работает
  SK> неправильно, например
 
 Hу.... стянутые интервалы всякие... А что это такое вообще - интервал стянутый в
 отрезок??? В точки может быть - дык интервал с совпадающими концами вроде как
 есть пустое множество, а значит FALSE... Так что вроде все правильно (уже ;)
 
  SK> Cross(xa,0,xb,0,xc,0,xd,0) - всегда true :( для льбых xa,xb,xc,xd
 
 пропатчено - см выше.
 
 Hу, Все! Пока Serge.
 
 --- GoldED/386 3.00.Alpha3+
  * Origin: 2+2=4 это не тождество, а выражение равное TRUE! (2:5080/169.35)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Отрезки   Eugene Yadrikhinsky   04 Jul 2001 21:00:00   Re: Отрезки   Andrew Ezhguroff   05 Jul 2001 02:14:08   Отрезки   Nick Gorinov   05 Jul 2001 09:02:21   Re: Отрезки   Serge Kanilo   06 Jul 2001 03:01:14   Re: Отрезки   Andrew Ezhguroff   06 Jul 2001 03:09:17   Отрезки   Egorov Pavel   12 Jul 2001 20:32:28   Re: Отрезки   Serge Kanilo   13 Jul 2001 01:52:24   Отрезки   Egorov Pavel   14 Jul 2001 00:38:56   Отpезки   Alexander Hritonenkov   05 Jul 2001 03:18:12   Отpезки   Roman Vorobets   06 Jul 2001 11:56:40   Отpезки   Pavel Girnov   05 Jul 2001 01:40:57   Отрезки   Maxim Plaksin   05 Jul 2001 01:12:12   RE:Отрезки   Vadim Ajuev   06 Jul 2001 01:19:29