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

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

HotLog


 
Вернуться
Тема: Невозможный треугольник. Баг теста?
1
  1  Дмитрий, 19 октября 2022 г. 18:12:59
      если кому интересно, то здесь для стороны С берется 12 знаков после запятой, а для всех остальных значений 13. то есть это даже не округление, 13-ая цифра 0, иначе число знаков было бы у всех по 13. при чем если координаты точек пропорционально изменять, то ошибка тоже не выпадает. но именно при заданных координатах сторона получается чуть больше полупериметра. на этом мои скромные знания питона заканчиваются, почему так получается до конца не понял. авторы задачи молодцы, а я пойду другую порешаю...

from math import *


def s(x1, y1, x2, y2, x3, y3):
a = pow(pow((x1 - x2), 2) + pow((y1 - y2), 2), 0.5)
b = pow(pow((x1 - x3), 2) + pow((y1 - y3), 2), 0.5)
c = pow(pow((x2 - x3), 2) + pow((y2 - y3), 2), 0.5)
p = (a + b + c) / 2
print(len(str(a)[str(a).index('.') + 1:]), # 13 знаков
len(str(b)[str(b).index('.') + 1:]), # 13 знаков
len(str(c)[str(c).index('.') + 1:]), # 12 знаков
len(str(p)[str(p).index('.') + 1:])) # 13 знаков
return pow(p * (p - a) * (p - b) * (p - c), 0.5)


x1, y1 = 100, 0
x2, y2 = 0, 100
x3, y3 = 725, -625
area = s(x1, y1, x2, y2, x3, y3)
print(area)
  2  Дмитрий, 19 октября 2022 г. 17:12:05
      по идее значение может быть только больше либо равно нулю и никогда меньше. без math пробовал решать пока не понял в чем проблема. по сути дело не в этом, комплексное число тоже не должно появляться. но при значениях 0 0 100 0 0 100 725 -625 действительно полупериметр оказывается меньше стороны b. пока не понял как это получается, попробую разобраться ради интереса. спасибо за ответы
  3  Хворых Павел, 19 октября 2022 г. 16:56:43
      Михаил, это значение может быть не только близко нулю, но и просто равно нулю. Ведь тестируемой точке ничто не мешает лежать на стороне треугольника, в результате получается нулевая площадь. Например, код Дмитрия вылетает с ошибкой на тесте 0 0 100 0 0 100 725 -625.
  4  Терентьев Михаил Павлович, 19 октября 2022 г. 15:48:53
      А по поводу способа решения: лучше такие задачи и вправду решать в целых числах. Погуглите про псевдоскалярное произведение векторов. С помощью него можно искать площадь параллелограмма, заданного векторами. А это удвоенная площадь треугольника.
  5  Терентьев Михаил Павлович, 19 октября 2022 г. 15:34:29
      Полагаю, что в том тесте значение p*(p-a)*(p-b)*(p-c) близко к нулю. А из-за погрешности оно может стать отрицательным. И при попытке возвести отрицательное число в вещественную степень (в 0.5) возникает исключение ValueError: math domain error. Примечательно, что если убрать подключение модуля math, то ошибки при извлечении корня не возникнет (получится просто некоторое комплексное число). Ошибка будет дальше в round при попытке округлить комплексное число.
  6  Дмитрий, 19 октября 2022 г. 14:06:29
      Михаил Павлович, не совсем понял, что вы написали. можно для самых маленьких и тупых?
вот это решение будет неверным пока в формуле Герона не поставить модуль. мне не дает покоя почему, ведь там не может быть отрицательного значения. можете объяснить в чем проблема? надеюсь ничего, если тут это выложу

from math import *

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())
x, y = map(int, input().split())


def s(x1, y1, x2, y2, x3, y3):
a = pow(pow((x1 - x2), 2) + pow((y1 - y2), 2), 0.5)
b = pow(pow((x1 - x3), 2) + pow((y1 - y3), 2), 0.5)
c = pow(pow((x2 - x3), 2) + pow((y2 - y3), 2), 0.5)
p = (a + b + c) / 2
return round(pow(p * (p - a) * (p - b) * (p - c), 0.5), 2)


s0 = s(x1, y1, x2, y2, x3, y3)
s1 = s(x, y, x2, y2, x3, y3)
s2 = s(x1, y1, x, y, x3, y3)
s3 = s(x1, y1, x2, y2, x, y)
if s0 < s1 + s2 + s3:
print('Out')
else:
print('In')
  7  Беляев Сергей Николаевич, 19 октября 2022 г. 13:40:47
      Эту задачу можно решить в целых числах :)
  8  Терентьев Михаил Павлович, 19 октября 2022 г. 13:32:51
      Хм, залил только что Героном на python. Написал отдельную функцию, считающую площадь по трем точкам. Ставил assert на подкоренные выражения, чтобы они были >= 0.0. Разве что в конце сравнивал сумму трех площадей и общую площадь с погрешностью 0.00001.
  9  Дмитрий, 19 октября 2022 г. 6:27:02
      ну и в целом - можно ли как-то узнать какие именно значения подставляет система в провалившемся тесте? я почти уверен, что нет, но мало ли...
  10  Дмитрий, 19 октября 2022 г. 6:23:33
      В задаче №102 "Треугольник и точка" в тесте №34 выпадала ошибка до тех пор, пока не начал брать формулу Герона по модулю. То есть ошибка появлялась из-за того, что полупериметр треугольника получался меньше одной из сторон и корень брался из отрицательного числа (для Python):

pow(abs(p * (p - a) * (p - b) * (p - c)), 0.5) не равно pow(p * (p - a) * (p - b) * (p - c), 0.5)

Но это же невозможно, разве нет? Полупериметр треугольника не может быть меньше его стороны. Что за невозможный треугольник подставляется системой в тесте №34, подскажите троечнику)
1

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

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