Elementary computational geometry

(Различия между версиями)
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
! Тесты для самостоятельного тестирования
 
! Тесты для самостоятельного тестирования
 
|-
 
|-
|[http://wiki.school.ioffe.ru/images/5/5e/Class-geometry.pdf Разные задачи на геометрические примитивы] || [https://207.154.240.40/cgi-bin/new-client?contest_id=341 Вход в тестирующую систему (контест 341)] || [http://wiki.school.ioffe.ru/images/8/8b/Problems_A_ZK.zip Задачи A...ZK]; [http://wiki.school.ioffe.ru/images/8/8b/Problems_ZL_ZV.zip Задачи ZL...ZV]
+
|[http://wiki.school.ioffe.ru/images/5/5e/Class-geometry.pdf Разные задачи на геометрические примитивы] || [https://207.154.240.40/cgi-bin/new-client?contest_id=341 Вход в тестирующую систему (контест 341)] || [https://prog.school.ioffe.ru/upload/problems.zip Все задачи]
 
|}
 
|}
  

Версия 00:05, 7 октября 2020

Содержание

Почитать

Материалы по вычислительной геометрии ЛКШ, 2010 г., параллель B' (там же глоссарий англ. терминов)
Подробные лекции по вычислительной геометрии на плоскости, Е.В. Андреева, Ю.Е. Егоров
Короткий справочник по скалярному и косому произведениям


Сдать тренировочные задачи

Cейчас на сервере есть возможность сдавать задачи на Python 3, C++ 17 и Java 8.

Условия задач Ссылка для входа Тесты для самостоятельного тестирования
Разные задачи на геометрические примитивы Вход в тестирующую систему (контест 341) Все задачи

Материалы некоторых занятий

Начало — классы Point, Vector (16 сентября 2020 г.)

class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return "({0}, {1})".format(self.x, self.y)


class Vector:

    # конструктор
    def __init__(self, a, b):
        if type(a) == Point and type(b) == Point:
            self.x = b.x - a.x
            self.y = b.y - a.y
        elif type(a) == int and type(b) == int:
            self.x = a
            self.y = b
        else:
            raise Exception("Неверно указан тип параметра при создании вектора!")

    def __str__(self):
        return "({0}, {1})".format(self.x, self.y)

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def scalar(self, other):
        return self.x * other.x + self.y * other.y


P = Vector(3, 4)
Q = Vector(1, 2)
print(P, Q, P + Q)
A = Point(3, 4)
B = Point(1, 2)
v = Vector(1, 3)
u = Vector(-1273548172564, 1)
print(v.scalar(u))

Скалярное и векторное (косое) произведение векторов, неправильная реализация метода Vector.polar() (23 сентября 2020 г.)

from math import atan, pi


class Point:

    # конструктор
    def __init__(self, *args):
        if len(args) == 1 and type(args[0]) == str:
            self.x, self.y = map(int, args[0].split())
        elif len(args) == 2 and type(args[0]) == int and type(args[1]) == int:
            self.x = int(args[0])
            self.y = int(args[1])
        else:
            raise Exception("Неверно указан тип параметров при создании точки!")


    def __str__(self):
        return "({0}, {1})".format(self.x, self.y)


class Vector:

    # конструктор
    def __init__(self, a, b):
        if type(a) == Point and type(b) == Point:
            self.x = b.x - a.x
            self.y = b.y - a.y
        elif type(a) == int and type(b) == int:
            self.x = a
            self.y = b
        else:
            raise Exception("Неверно указан тип параметра при создании вектора!")

    def __str__(self):
        return "({0}, {1})".format(self.x, self.y)

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def scalar(self, other):
        return self.x * other.x + self.y * other.y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def polar(self):
        one = Vector(1, 0)
        return one.cross(self) / one.scalar(self)

def dist(A, B):
    return ((A.x  - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ** 0.5

A = Vector(*map(int, input().split()))
print(A.polar())

Разбор задачи про вычисление полярного угла точки (30.09.2020)

Фото с доски: использование знаков скалярного и косого произведений

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты