Найти - Пользователи
Полная версия: Медленное выполнение программы
Начало » Центр помощи » Медленное выполнение программы
1
dingo
Задача очень простая
Нужно вычислить находиться точка в треугольнике или нет
Входной файл
Дано N количество тестов
Далее следует N*2 строк координаты треугольника x1 y1 x2 y2 x3 y3 и координаты точки x0 y0
Как можно ускорить этот код
from decimal import *
def check(x1,y1,x2,y2,x3,y3,x0,y0):
    x1=Decimal(x1)
    y1=Decimal(y1)
    x2=Decimal(x2)
    y2=Decimal(y2)
    x3=Decimal(x3)
    y3=Decimal(y3)
    x0=Decimal(x0)
    y0=Decimal(y0)
    sample=((x1*y2*1)+(y1*1*x3)+(1*x2*y3)-(1*y2*x3)-(y1*x2*1)-(x1*1*y3))/2
    if sample<0:
        sample*=-1
    test1=((x0*y2*1)+(y0*1*x3)+(1*x2*y3)-(1*y2*x3)-(y0*x2*1)-(x0*1*y3))/2
    test2=((x1*y0*1)+(y1*1*x3)+(1*x0*y3)-(1*y0*x3)-(y1*x0*1)-(x1*1*y3))/2
    test3=((x1*y2*1)+(y1*1*x0)+(1*x2*y0)-(1*y2*x0)-(y1*x2*1)-(x1*1*y0))/2
    if test1<0:
        test1*=-1
    if test2<0:
        test2*=-1
    if test3<0:
        test3*=-1
    if test1+test2+test3==sample:
        return "YES\n"
    else:
        return "NO\n"
f=open("trianglep.in")
l=f.read()
f.close()
s=l.split()
base=int(s[0])
set=1
f=open("trianglep.out","w")
for i in xrange(base):
    f.write(check(s[set],s[set+1],s[set+2],s[set+3],s[set+4],s[set+5],s[set+6],s[set+7]))
    set+=8
f.close()
fata1ex
Алгоритмы:
http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle
http://nerdparadise.com/math/geometry/pointinatriangle/
http://www.blackpawn.com/texts/pointinpoly/default.html
http://mathforum.org/library/drmath/view/54505.html

По коду, можно не использовать decimal. Зачем умножать на 1? Зачем вычислять одни и те же произведения несколько раз? Что за ужас происходит внизу я вообще боюсь смотреть :)

Считывание можно организовать так:
with open('in', 'r') as fin, open('out', 'w') as fout:
    N = int(fin.next())
 
    for case_idx in xrange(1, N + 1):
        try:
            case = map(int, fin.next().split())
            triangle = zip(case[::2], case[1::2])
            point = triangle.pop()
 
        except StopIteration:
            pass
 
        else:
            result = is_in_triangle(triangle, point)
            fout.write('Case {0}: {1}'.format(case_idx, result))

А по алгоритму выбирайте любой удобный. И именуйте нормально переменные, постить такой код на форум - неуважение к читающим его :(
odnochlen
Почему бы не передавать треугольник списком точек, а точку кортежем или обьектом? А то глаза режет, как fatalex уже написал.
gisolog
Проверка принадлежности точки полигону: Отсюда
# determine if a point is inside a given polygon or not
# Polygon is a list of (x,y) pairs.
def point_inside_polygon(x,y,poly):
    n = len(poly)
    inside =False
    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x,p1y = p2x,p2y
    return inside
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB