Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.08.2010, 14:30
Новичок

Отправить личное сообщение для LGod Посмотреть профиль Найти все сообщения от LGod
 
Регистрация: 08.04.2010
Сообщений: 14

Треугольники
На плоскости задано N точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить K - количество треугольников с вершинами в заданных точках и целочисленной площадью.
0 < N, |Xi|,|Yi| <= 5000.
Лимит времени: 0.1 секунды
Лимит памяти: 64 MB
  #2  
Старый 19.08.2010, 15:25
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Формулу для площади через векторное произведение знаете?
Если да, то квадратичный (O(N^2))алгоритм получится
  #3  
Старый 19.08.2010, 15:29
Новичок

Отправить личное сообщение для LGod Посмотреть профиль Найти все сообщения от LGod
 
Регистрация: 08.04.2010
Сообщений: 14

Я даже не знаю что такое векторное произведения=)
  #4  
Старый 19.08.2010, 15:35
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

S = |(x1 – x3)·(y2 – y3) – (x2 – x3)·(y1 – y3)|/2
  #5  
Старый 20.08.2010, 03:48
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Функция принимает параметрами указатели на массивы координат точек и их общее количество. Разность в формуле заменена исключающим или, а умножение логическим и, часть вычислений вынесена из третьего цикла во второй, если посмотреть на формулу выше, станет ясно зачем мы делаем & 1.
Код:
int xyn2k( int *x, int *y, int N )
{
    int K = 0;
    for( int i = 0; i < N - 2; i++ )
        for( int j = i + 1; j < N - 1; j++ )
        {
            int dx = x[ i ] ^ x[ j ], dy = y[ i ] ^ y[ j ];
            for( int k = j + 1; k < N; k++ )
                K += !( ( ( y[ i ] ^ y[ k ] ) & dx ^ dy & ( x[ i ] ^ x[ k ] ) ) & 1 );
        }
    return K;
}
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбиение сферы на треугольники Anonymous Вычислительная геометрия 11 04.01.2010 23:41
Разделение таблицы на треугольники гость Задачи 0 03.12.2009 13:21
Треугольники гость Задачи 1 14.09.2009 14:16