ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1469. Не курить!

What's the "good" algo for this problem
Послано Todor Tsonkov 25 сен 2006 01:03
I coded for 10 minutes brute force which got TL on test 4.. any ideas about the "good" algo ?
Re: What's the "good" algo for this problem
Послано Ilya Rasenstein (Lyceum #40) 25 сен 2006 21:04
Surely! std::set 4ever!
Re: What's the "good" algo for this problem
Послано Todor Tsonkov 25 сен 2006 21:32
Haha :) Some more hints ;)
Read Cormen's "Introduction to Algorithms" (-)
Послано Vladimir Yakovlev (USU) 25 сен 2006 23:36
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано Ilya Rasenstein (Lyceum #40) 26 сен 2006 10:54
You can implement stuff, described in Cormen, easily, using set. That's what I was trying to say.
Ilya Razenshteyn.
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано Vedernikoff Sergey 6 окт 2006 13:41
There is obvious "slide line" algo, that can be applied in O(NlogN). But there is a little problem here: perpendicular to ox line segments...
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано EfremovAleksei 13 ноя 2006 16:35
It's not problem! I don't exam this case and got AC.
No subject
Послано Todor Tsonkov 15 ноя 2006 14:31
Can you explain a little more about this algo ?
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано Thunder 1 апр 2007 16:13
This isn't problem too. Just rotate all points by the constant angle.

const
  angle=pi/60;
var
  x,y,buf1,buf2:real;
begin
...
  Buf1:=x;
  Buf2:=y;
  x:=Buf1*cos(angle)-Buf2*sin(angle);
  y:=Buf1*sin(angle)+Buf2*cos(angle);

Edited by author 01.04.2007 16:14
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано svr 13 июл 2007 17:09
I solved for me the little problem of vertical segments by
applying affine matrix
[2 3]
[5 -7]
or any other to given coordinates.
As result algo from Cormen can be taken without any changes.

Edited by author 13.07.2007 17:09
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано Lomir 14 июл 2007 00:43
As far as me, I used some my heuristics with vertical segments:
First, when reading points i makred point with lesser x cordinate as enter point.
I sorted points by X, and if X are eual then sorted by enter mark.
This assumes then enterpoint will be before exitpoint of segment in set.
Re: Read Cormen's "Introduction to Algorithms" (-)
Послано Denis Koshman 30 авг 2008 04:41
Vertical segments are easy to treat. Just sort X ascendingly and for equal X sort Y ascendingly. When you add vertical segment, consider its topmost Y coordinate during comparisons, and when you add some other segment, assume equality when its scan-line ordinate is compared to that one of vertical segment in the set.

Such behavior is identical to the one we'd apply to the segments set after rotating it for small enough angle. Another way to see that - apply skew affine transform

x2 = x+y*1e-6
y2 = y

and see how formerly vertical segments are handled in this case.

Edited by author 30.08.2008 04:52