Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.05.2009, 00:52
Новичок

Отправить личное сообщение для AlterEgoMan Посмотреть профиль Найти все сообщения от AlterEgoMan
 
Регистрация: 28.05.2009
Сообщений: 4

Зацените задачку
Вот уже третий день ломаю голову над задачей

Есть N (1<=N<=100) треугольников заданых координатами на плоскости. Требуется найти точку (одну из них), лежащую в области пересечения наибольшего количества треугольников?

Есть какие то идеи?
  #2  
Старый 28.05.2009, 00:59
гость

 
Сообщений: n/a

Ну, найди все точки пересечения любых пар отрезков сторон треугольников, и посчитай во скольких треугольниках каждая из них находится => сложность O(n^3).
  #3  
Старый 28.05.2009, 01:00
гость

 
Сообщений: n/a

И называйте свою тему поконкретнее в следующий раз!!!
Если задача с какого-то онлайнового ресурса, приводите ссылку!
  #4  
Старый 28.05.2009, 01:30
Новичок

Отправить личное сообщение для AlterEgoMan Посмотреть профиль Найти все сообщения от AlterEgoMan
 
Регистрация: 28.05.2009
Сообщений: 4

А что делать когда треугольники находятся один в другом (не пересекаются)?
  #5  
Старый 28.05.2009, 01:36
гость

 
Сообщений: n/a

Хм, да, я забыл про этот случай....
Но достаточно просто еще рассмотреть 3n точек - все вершины треугольников.
  #6  
Старый 28.05.2009, 01:42
Новичок

Отправить личное сообщение для AlterEgoMan Посмотреть профиль Найти все сообщения от AlterEgoMan
 
Регистрация: 28.05.2009
Сообщений: 4

Идея отличная!
Спасибо за помощь!
  #7  
Старый 28.05.2009, 01:42
Новичок

Отправить личное сообщение для AlterEgoMan Посмотреть профиль Найти все сообщения от AlterEgoMan
 
Регистрация: 28.05.2009
Сообщений: 4

Тема закрыта
 


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

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите реализовать следующую задачку на C# гость Реализация, исходники, языки 1 06.04.2009 18:51
помогите запрограммировать задачку Белочка) Задачи 3 11.01.2009 21:23
помогите решить задачку по указателям и функциям. sercul Математические алгоритмы 1 17.11.2008 01:14
Помогите решить задачку в с++ MermaidAlyona Оффтопик 1 30.10.2008 13:15
помогите плиз решить задачку Daiver Математические алгоритмы 2 22.04.2007 18:45