Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Андреев Антон Антонович, 21 марта 2020 г. 9:28:16
     А что в 21ом тесте? Голову ломаю, но не получается
  2  Вінівітін Артем Дмитрович, 17 февраля 2020 г. 22:06:58
     Тест 0 0 0 0 0 0 1 1 моя программа не проходит , но AC
     Это не треугольник. В тестах треугольники гарантированно невырожденные.
  3  Ковешников Глеб Юрьевич, 02 марта 2018 г. 18:13:47
     в обсуждении ни разу не сказали, что можно составлять уравнение прямых и смотреть знаки оставшихся двух точек
  4  Дашков Тарас Андреевич, 25 ноября 2013 г. 20:28:01
     С первого раза!)))
На самом деле задача простая, но это не всем очевидно (это касалось и меня).
Итак у нас есть 3 заданные координатами точки - вершины треугольника A,B,C и точка F, расположение которой относительно треугольника нужно определить.
Есть много способ как можно решить эту задачу, но по моему мнению самым простым является метод площадей.
Но каким бы ни был способ решения в начале необходимо проверить не лежит ли точка F на одной из вершин треугольника АВС, если лежит то сразу вывести "In", иначе выполнить следующие действия.
Нужно найти площадь большого треугольника, а затем сравнить его площадь с сумой площадей треугольников, образованных вершинами большого треугольника и точкой F. То есть S(AFB)+S(BFC)+S(AFC)-S(ABC) <= 0.
Есть много формул, но я представлю самую быструю и простую в использовании, которую некогда представил администратор.
Переменные, представленные в формуле соответствуют переменным условия задачи: модуль((x1-x2)*(y3-y2)-(y1-y2)*(x3-x2))/2 (если что то не так пусть
     По этому поводу скажу так же, что вовсе необязательно отдельно проверять принадлежность точки стороне, а вместо площадей можно считать двойные площади, так можно решить задачу в целых числах.
  5  Олейник Ярослав Николаевич, 01 февраля 2013 г. 21:43:17
     Довольно короткое решение через вектора
  6  Леонов Олег Андреевич, 29 марта 2012 г. 18:06:39
     Местный компилятор ( C++ ) поддерживает inline-функции?
     Да
  7  Фоменко Владимир, 14 марта 2012 г. 10:38:41
     Всем, кто пишет на c++ не советую использовать функции библиотеки math.h такие, как abs - из-за них как раз тоже полно ошибок!
  8  Полянских Сергей, 16 февраля 2011 г. 7:24:52
     Поясните условие: если точка находится на границе треугольника, это не тоже самое что точка внутри.
Не проще ли написать "не снаружи" вместо внутри. Тогда условие будет понятней, а то лично я не учел этот случай когда читал условие. Ведь внутри и на границе это не совместимые вещи.
     Нужно выводить In, когда точка принадлежит треугольнику, т.е. либо на границе, либо строго внутри.
  9  Daniyar Maminov, 15 февраля 2011 г. 18:34:15
     А что такое Декартовая система?
     Обычная, которую школьники используют.
  10  Хисамутдинов Расим Рустамович (РБЛИ), 18 января 2011 г. 9:48:08
     Можно использовать формулу Герона?
     Можно, но можно и косое произведение тоже использовать для вычисления площади (проще и эффективнее).
  11  Ваян B B, 18 сентября 2010 г. 9:49:26
     а отрицательный координаты могут быть?
     Могут, ведь ограничения указаны на абсолютные значения, а это фактически по модулю.
  12  Бормотов Виталий Борисович, 24 ноября 2008 г. 13:05:13
     Да она ж почти так же, как "Дачники" решается! Я чуть-чуть изменил, и прошло. И целочисленными вычислениями вполне можно обойтись.
  13  Астапов Александр Сергеевич, 14 января 2008 г. 21:43:56
     Что в первом тесте?
     Первый тест: -2 -2 3 1 0 1 0 0
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru