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

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

HotLog


 

Треугольные страны

(Время: 1 сек. Память: 16 Мб Сложность: 37%)

Эта история происходила на одной плоской планете. С незапамятных времен на ней существовал город N, находящийся в точке xn,yn. Кроме этого, в разное время на этой же планете существовали страны, каждая из которых имела форму треугольника.

Теперь перед историками встала серьезная задача — по имеющимся у них данным о треугольных странах определить, в какие страны мог входить город N. Город мог входить в страну, если он находится строго внутри нее.

Входные данные

Первая строка входного файла содержит два числа: xn и yn — координаты города N. Вторая строка входного файла содержит количество k треугольных стран (1 ≤ k ≤ 1000). Последующие k строк каждая описывают одну треугольную страну. Описание треугольной страны состоит из шести целых чисел x1,y1,x2,y2,x3,y3, где (x1,y1), (x2,y2), (x3,y3) — координаты вершин этой страны.

Гарантируется, что все страны имеют ненулевую площадь. Все координаты не превосходят 10000 по абсолютной величине.

Выходные данные

В первой строке выходного файла выведите количество стран, в которые мог входить город N. Во второй строке выведите через пробел номера этих стран в возрастающем порядке. Страны нумеруются с единицы в том порядке, в каком они заданы во входном файле.

Примеры

INPUT.TXTOUTPUT.TXT
10 1
2
-2 0 2 0 0 2
-3 0 3 0 0 3
2
1 2
20 2
2
-2 0 2 0 0 2
-3 0 3 0 0 3
1
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Геометрия - 1
 Геометрия - 2
 A. Площадь треугольника
 B. Прямоугольник - 2
 C. Треугольные страны
 D. Алтайский технический университет
 E. Площадь треугольника - 2
 F. Треугольная область
 G. Треугольник и окружности
 H. Вписанная окружность

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



Джозз вход на официальный сайт