Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2005-11-28 22:06:35

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Свежее мясо или Нові задачі

Раз уж наверху написано,что олимпиада будет через неделю,то предлагаю не отрофировать мозги и порешать всем задачку...
Итак...

Код:

На координатній площині горізонтальними та вертикальними лініями,
що проходять через точки з цілочисленними координатами утворено
сітку розміром клітинок 1х1.На цій площині зображено трикутник.

Написати программу,яка за заданними координатами вершин трикутника
підраховує кількість клітинок координатної сітки,що потрапили в межі
трикутника повністю (допускається щоб вершини або сторони клітин 
лежали на сторонах трікутника)

Вхідні дані:
вхідний текстовий файл містить три рядки, у кожному з яких вказано 
2 числа - координати вершини трикутника

Вихідні дані:
Вихідний текстовий файл має містити єдиний рядок з кількістю клітинок

Приклад:
Вхідні дані:                 Вихідні дані:
0 0                              3
0 3
4 0

Відредаговано jack_spektor (2005-11-28 22:11:04)


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#2 2005-11-28 23:06:15

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

Не бойся, пока у меня не первое место на тимусе, мои мозги не атрофируются :-)


ICQ 233-416-344

Поза форумом

 

#3 2005-11-29 20:52:36

Anna
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-06
Повідомлень: 122

Re: Свежее мясо или Нові задачі

Думаешь, он о твоих мозгах заботится? Что-то я сомневаюсь... По-моему, тут причина в другом... smile


Хорошо смеется тот, кто смеется последним...

Поза форумом

 

#4 2005-11-29 22:26:01

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Свежее мясо или Нові задачі

Не корысти ради...
Просто на прошедшей районной олимпиаде такая задача была и интересно кто-как её бы решил...
Сам пробовал,да в голову чтото решение не лезет...

Предлагаю конкурс на самое короткое решение :-)
Что-то никак не могу понять...Как эти морды,в смысле смайлики ставить?

Відредаговано jack_spektor (2005-11-29 22:28:31)


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#5 2005-11-30 17:53:20

Sharp
Олімпієць
Зареєстрований: 2005-10-17
Повідомлень: 34

Re: Свежее мясо или Нові задачі

Можно попробовать найти две крайние точки по оси абсцисс, затем Брезенхема одновременно по "длинной" линии и 2 "коротким", вычитая координаты Y следующих точек друг из друга (если они не совпадают) и еще 1 можно получить, сколько вертикально расположенных клеток находится между n и n+1. Суммируя их все можно получить искомое число.

Поза форумом

 

#6 2005-11-30 18:58:05

Gluk
Олімпієць
Зареєстрований: 2005-11-20
Повідомлень: 19

Re: Свежее мясо или Нові задачі

было бы немного логично указать ограничения... тогда бы было понятно какого плана решение надо искать...

могу предложить довольно оптимальный и несложно реализуемый вариант....
допустим есть ф-ция inside (x,y), которая определяет лежит ли точка (x,y) внутри треугольника

тогда функцию count (x1, y1, x2, y2), которая считает сколько клеточек из прямоугольника x1,y1,x2,y2 лежит внутри треугольника, можно описать приблизительно так:

count (x1, y1, x2, y2)
  if (x1==x2) return 0
  if (y1==y2) return 0
  if (inside (x1, y1) and inside (x2, y1) and inside (x1, y2) and inside (x2, y2) ) return (x2-x1)*(y2-y1)
 
  if ( ((x2-x1)==1)  and  ((y2-y1)==1) ) return 0

  cx = (x1+x2)/2
  cy = (y1+y2)/2
  return count (x1, y1, cx, cy)+count (cx, y1, x2, cy)+count (x1, cy, cx, y2) +count (cx, cy, x2, y2)


ну и ответ самой задачи
  count (min (x1,x2,x3), min (y1,y2,y3), max (x1,x2,x3), max (y1,y2,y3))

где (x1,y1), (x2,y2), (x3,y3)  - координаты вершин треугольника

Відредаговано Gluk (2005-11-30 19:26:02)

Поза форумом

 

#7 2005-11-30 20:48:00

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

Я мог бы указать вам на ошибки.
Я мог бы растрепать об этом всем.
Однако вижу - как талант вы хлипки.
А значит напишу: "КГ/АМ"!

Шучу, шучу... Просто вот о чем я подумал: сложность алгоритма то О(граница треугольника)
А дело вот в чем: за такую сложность можно и полегче решить.


ICQ 233-416-344

Поза форумом

 

#8 2005-11-30 21:10:00

Gluk
Олімпієць
Зареєстрований: 2005-11-20
Повідомлень: 19

Re: Свежее мясо или Нові задачі

Ivan написав:

Я мог бы указать вам на ошибки.
Я мог бы растрепать об этом всем.
Однако вижу - как талант вы хлипки.
А значит напишу: "КГ/АМ"!

Шучу, шучу... Просто вот о чем я подумал: сложность алгоритма то О(граница треугольника)
А дело вот в чем: за такую сложность можно и полегче решить.

не спорю.... просто все зависит от того кому что легче писать smile

Поза форумом

 

#9 2005-11-30 21:57:29

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

Ну, если тебе легче понавыдумывть что нибудь вместо очевидного решения, то соглаен...


ICQ 233-416-344

Поза форумом

 

#10 2005-11-30 22:23:04

Gluk
Олімпієць
Зареєстрований: 2005-11-20
Повідомлень: 19

Re: Свежее мясо или Нові задачі

Ivan написав:

Ну, если тебе легче понавыдумывть что нибудь вместо очевидного решения, то соглаен...

ок - ок... и какое очевидное решение ты предлагаешь ? wink ты там все аккуратно выведи... сам увидишь что не все так просто..........

Поза форумом

 

#11 2005-12-01 10:27:10

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Свежее мясо или Нові задачі

В умові не сказано, якими є координати вершин трикутника.

Якщо вони гарантовано цілі, то це задача "Велика Трикутна Область" УОІ-2003, є розв'язок за O(log(m+n)), пояснення можна подивитися на www.uoi.kiev.ua (зайти на сторінку Всеукра 2003 р., там внизу лінк на архів олімпіади).

Якщо не обов'язково цілі, то я не знаю розв'язку, кращого за theta(min(m,n)) (але це _не_ гарантує, що такого розв'язку нема взагалі.). Така задача описана у багатьох місцях, і, зокрема, у моїй книжечці, що вийшла минулого літа у "Шкільному світі".

Коротко суть розв'язку за theta(min(m,n)):
0) якщо трикутник "низенький і широкий", повертаємо його на 90 градусів (або транспонуємо)
1)
for усіх ("стовпчиків" від x_i до (x_i)+1) do begin
  знаходимо точки перетину сторін трикутника з цими (x_i та (x_i)+1) верт. прямими, заокруглюємо нижні y-координати вгору й беремо максимум з двох, верхні y-координати вниз і беремо мінімум з двох, рахуємо зрізану різницю між ними (де "зрізана різниця" означає: якщо різниця менша нуля, вважаємо її нулем).
end
Сума усіх таких "зрізаних різниць" і є відповіддю.

Поза форумом

 

#12 2005-12-01 16:16:43

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

Хочу добывить, что БТО получается не сразу, просто надо сперва вписать треугольник в квадрат, а в нем выделить три прямоугольных треугольника и исходный треугольник, а затем подсчитать разность


ICQ 233-416-344

Поза форумом

 

#13 2005-12-01 17:34:12

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Свежее мясо или Нові задачі

Товарищи! Эта задача в той формулировке, в которой она дана, СЛОЖНЕЕ БТО!!!
В БТО давался ПРЯМОУГОЛЬНЫЙ треугольник, а у на произвольный. Поэтому нужно вписать треугольник в квадрат и вычитать три прямоугольных треугольника. Но тут есть один прикол. В БТО находилось число клеток ВНУТРИ треугольника, поэтому если мы вычтем из квадрата эти три треугольника, то получим кол-во квадратиков ВНУТРИ И НА ГРАНИЦЕ начального. Нам нужно еще вычесть и число клеток на границе. Тут можно усовершенствовать БТО, но есть одна проблема - иногда мы будем вычитать клеточки границы дважды. Особенно это чувствуется на узких треугольниках. Попробуйте, например, для треугольникв (0,0),(3,5),(5,3). В нем у самого острого угла две клеточки вычитаются дважды!!! Поэтому БТО тут не проходит sad

Поза форумом

 

#14 2005-12-01 17:50:38

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

Нет. По моему, тут БТО прекрасно катит, нужно просто сделать именно то, что ты сказал и все


ICQ 233-416-344

Поза форумом

 

#15 2005-12-01 18:04:08

Батыев Андрей
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 70

Re: Свежее мясо или Нові задачі

По условию написано, что нужно считать все клетки, которые лежат ПОЛНОСТЬЮ в пределах треугольника. Поэтому просто квадрат минус 3 БТО тут не катят! (с границей тут реальная сложность)

В принципе, можно поиздеваться с площадью треугольника, а так же кол-вом клеток, которые покрывают стороны треугольника. Тогда время работы O(1)!

Відредаговано Батыев Андрей (2005-12-01 18:08:08)

Поза форумом

 

#16 2005-12-01 18:20:51

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: Свежее мясо или Нові задачі

не верится мне в О(1) все равно НОД надо искать (чтобы найти число целых точек на грнице)


ICQ 233-416-344

Поза форумом

 

#17 2005-12-01 18:54:55

Джулгаков Дмитрий
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-03
Повідомлень: 61

Re: Свежее мясо или Нові задачі

Вся проблема в том, как "поиздеваться" над границей треугольника. Короче говоря, основная задача - для острого угла, лежащего внутри одной четверти найти количество клеток, которые пересекают обе стороны угла. Тогда задача решена. Но именно в этом моменте и вся проблема!

Поза форумом

 

#18 2005-12-01 22:51:48

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Свежее мясо или Нові задачі

Странно то,что эта задача была на районной олимпиаде.
Вообще на районке в этом году учудили...
Две задачи и из них одна - эта...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#19 2005-12-01 23:04:35

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Свежее мясо или Нові задачі

Задания 2 тура появились.
Ссылка тоже


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt