Есть задача: В первой строке задано два целых числа 1≤n≤50000 и 1≤m≤50000 — количество отрезков и точек на прямой, соответственно. Следующие n строк содержат по два целых числа ai и bi (ai ≤ bi) — координаты концов отрезков. Последняя строка содержит m целых чисел — координаты точек. Все координаты не превышают 10^8 по модулю.
Точка считается принадлежащей отрезку, если она находится внутри него или на границе. Для каждой точки в порядке появления во вводе выведите, скольким отрезкам она принадлежит. Я придумал решение: Сортируем отрезки по началу. Далее бежим по точкам и по отрезкам. Смотрим, если точка принадлежит отрезку, то увеличиваем счетчик, и отмечаем, что она принадлежит хотя бы одному отрезку.
Далее смотрим, если случилось так, что точка не принадлежит какому-то отрезку, но хотя бы одному принадлежит, то всем последующим она тоже не принадлежит. (т.к. отрезки по возрастанию начальных координат). Но у меня проблема с одним тестом:
[6 6] [2 3] [2 5] [3 5] [2 7] [5 7] [3 7]
- отрезки, 1 2 3 5 6 7 — точки. Выдает 0 3 5 5 1 1, когда ответ 0 3 5 5 3 3. Хочу узнать, где ошибка в моем алгоритме. И если она есть, то натолкнуть меня на верное решение 🙂 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*;
import static java.lang.Integer.parseInt; /** * Created by Andrey on 31.12.2018. */ public class Stepic < static int scanInt() throws IOException < return parseInt(scanString()); >static String scanString() throws IOException < while (tok == null || !tok.hasMoreTokens()) < tok = new StringTokenizer(in.readLine()); >return tok.nextToken(); > static BufferedReader in; static StringTokenizer tok; public static void main(String[] args) throws IOException < in = new BufferedReader(new InputStreamReader(System.in)); int n = scanInt(); int m = scanInt(); int[] ans = new int[m]; Listsegments = new ArrayList<>(); for(int i = 0 ; i < n; i++)< segments.add(new Segment(scanInt(),scanInt())); >segments.sort(Comparator.comparingInt(o -> o.x)); int[] dots = new int[m]; boolean[] dotsB = new boolean[m]; for(int i = 0; i < m; i++)< dots[i] = scanInt(); >for(int i = 0; i < dots.length; i++)< for (Segment segment : segments) < if (segment.x = dots[i]) < ans[i]++; dotsB[i] = true; >else < if (dotsB[i]) < break; >> > > for(Segment segment : segments) < System.out.println(segment.x + » » + segment.y); >for (int an : ans) < System.out.print(an + » «); >> public static class Segment < public int x; public int y; public Segment(int x, int y) < this.x = x; this.y = y; >> >
Отслеживать
Dr. kott9ra
задан 31 дек 2018 в 13:24
Dr. kott9ra Dr. kott9ra
43 8 8 бронзовых знаков
В принципе нет необходимости сортировать отрезки.
31 дек 2018 в 13:29
И что за белиберда у вас с «правильным ответом»? Правильный ответ 0 3 5 5 4 3 , а не 0 3 5 5 3 3 . Точка 6 принадлежит 4 отрезкам, а не 3.
Точка, прямая и отрезок. 1 часть. 7 класс.
Определить, принадлежит ли точка с заданными координатами графику функции
1 янв 2019 в 20:19
Неверная проверка принадлежности. В геометрии есть формулы, используемые для проверки принадлежности точки отрезку. Не надо изобретать к ним свои. Плюс, нет смысла в сортировке.
2 янв 2019 в 8:00
2 янв 2019 в 9:16
2 янв 2019 в 9:52
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Далее смотрим, если случилось так, что точка не принадлежит какому-то отрезку, но хотя бы одному принадлежит, то всем последующим она тоже не принадлежит. (т.к. отрезки по возрастанию начальных координат).
Это неверно. Допустим у нас есть отрезки [0 100] [10 20] [40 80] . Они отсортированы по началам. Точка 50 принадлежит первому отрезку, не не принадлежит второму. Из этого вы делаете странный вывод, что «всем последующим она тоже не принадлежит». Но это не верно. Она принадлежит [40 80] .
Ваш подход, даже будучи реализованным правильно, будет очень неэффективным, ибо выполняет поиск в полном массиве отрезков для каждой точки. То, что отсортированность массива отрезков дает вам возможность завершить поиск раньше на основе проверки условия segment.x > dots[i] , помогает, но погоды не делает. В среднем вам придется проверять половину всех отрезков для каждой точки.
Вы пытаетесь реализовать on-line алгоритм, т.е. алгоритм, который обрабатывает каждую точку независимо от остальных точек. Не нужно этого делать, когда вам в условии ясно сказано, что задача является off-line, т.е. все тестовые точки заранее известны. Off-line решение всегда будет эффективнее on-line решения (или, по очевидным причинам, не хуже его).
Если бы стояла задача построить on-line решение, то эффективным подходом было бы построение такой классической структуры данных, как дерево отрезков. Вашей сортировкой отрезков вы фактически делаете шаг в этом направлении. Но, еще раз, в рамках вашей постановки задачи нет смысла тратить на это усилия.
Эффективное off-line решение данной задачи может основываться на классическом принципе слияния двух отсортированных массивов. Оба массива — и отрезков, и точек — надо отсортировать заранее, а затем синхронным проходом по обоим массивам получить ответ задачи. Структура алгоритма напоминает также алгоритм сканирующей прямой в одномерном варианте (поддерживает множество «активных» отрезков).
#include #include #include #include #include int main() < unsigned n, m; std::cin >> n >> m; using Segment = std::pair; std::vector segments(n); for (Segment > segment.first >> segment.second; std::vector points(m); std::vector counts(m); for (int > point; // Сортируем отрезки по началам std::sort(segments.begin(), segments.end()); // Сортируем точки (через индексный массив) std::vector point_index(m); std::iota(point_index.begin(), point_index.end(), 0u); std::sort(point_index.begin(), point_index.end(), [ return points[li] < points[ri]; >); // Заводим список активных отрезков — упорядочен по концам отрезков auto cmp_second = [](const Segment *lhs, const Segment *rhs) < return lhs->second < rhs->second; >; std::multiset active_segments(cmp_second); // Изначально этот список пуст auto it_segment = segments.begin(); for (unsigned i_point : point_index) < // Очередная точка int point = points[i_point]; // Поддерживаем список активных отрезков // Удаляем уходящие отрезки . while (!active_segments.empty() (*active_segments.begin())->second < point) active_segments.erase(active_segments.begin()); // . и добавляем приходящие отрезки for (; it_segment != segments.end() it_segment->first second >= point) active_segments.insert( // Ответ для текущей точки — количество активных отрезков counts[i_point] = active_segments.size(); > for (unsigned count : counts) std::cout
Правильный ответ на вашем входе, кстати, 0 3 5 5 4 3 , а не 0 3 5 5 3 3 .
Источник: ru.stackoverflow.com
Как проверить принадлежит ли точка отрезку
Сегодня мы рассмотрим еще одну типовую задачу из серии геометрические алгоритмы. Напишем функцию, которая будет проверять принадлежность произвольной точки отрезку, заданному координатами своего начала и конца.
Для реализации операций сравнения над вещественными данными напишем еще две функции: функцию EqPoint(), которая ,будет проверять, совпадают ли две точки на плоскости и функцию RealMoreEq() , которую будем использовать для проверки отношения «>=» (больше или равно). Причина ввода специальных функций нам уже известна.
Задача. Проверить, принадлежит ли точка отрезку.
Пусть точки — начальная и конечные точки отрезка. — произвольная точка на плоскости.
Вектор с началом в точке и концом в точке будет иметь координаты (x2-x1, y2-y1).
Если P(x, y) – произвольная точка, то координаты вектора равны: (x-x1, y – y1).
Точка Р будет принадлежать отрезку если:
- Векторы в и коллинеарны (равно нулю их векторное произведение):
, т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1) = 0 - Абсцисса точки P удовлетворяет условию: или . Иначе точка будет находиться на прямой левее или правее отрезка.
Результаты выполнения программы.
Введите координаты точек: x1, y1, x2, y2, x,y
0.5 1 2.5 2.8 1.203 1.633
Да.
Результаты тестирования в программе GeoGebra:
Сегодня мы написали функцию AtOtres() , которая проверяет принадлежность произвольной точки отрезку, заданному своими координатами.
Ввели еще две функции: EqPoint() и RealMoreEq() для реализации операций сравнения над вещественными данными. Первая проверяет, совпадают ли две точки на плоскости, вторая — используется для проверки отношения «>=».
На следующем уроке, на основе ранее написанных процедур, напишем процедуру определения координат точки пересечения двух отрезков.
На этом я с вами прощаюсь. До встречи на следующем уроке.
Спасибо, сам уже догадался до этого.. .
Кому интересно вот пример (не полный листинг) :
var
Form1: TForm1;
start:integer;
back:TBitmap;
AB,Am,Bm:real;
function LLine(x1,y1,x2,y2:real):real;
begin
LLine:=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
end;
У меня есть некая база отрезков (steps) маршрута:
У меня есть координаты точки, которая точно принадлежит к одному из указанных маршрутов. Как мне узнать, к какому участку маршрута принадлежит точка?
- Вопрос задан более трёх лет назад
- 3056 просмотров
Важно отметить!
Исходная точка может не находится на прямой между парами участка.
Пример отрезка:
Можно переиначить вопрос:
как найти диапазон точек между двумя парами координат учитывая топографию местности (Google Map API v3 DirectionsRenderer)?
Источник: 4systems.ru
Научный форум dxdy
Последний раз редактировалось PPrivett 30.07.2011, 20:02, всего редактировалось 1 раз.
Даны x1, x2 — начало и конец отрезка. Неупорядочены, т.е. может быть x1 > x2, а может быть и наоборот, а может быть и равенство. Также дан x3.
Определить, входит ли x3 в отрезок с концами в x1 и x2 за наименьшее количество операций, используя простые функции типа суммы, разности, сравнения, может быть модуля. (Подразумевается, что это в программе все делается на каком-то языке).
Какое наименьшее количество операций сравнения потребуется для выполнения задачи? Как найти наименьшее кол-во операций сравнения и обосновать? — это больше всего интересует.
Разумеется, интересует какой-нибудь не очевидный способ.
Re: Определить принадлежность точки отрезку.
30.07.2011, 21:50
Последний раз редактировалось ИСН 30.07.2011, 21:51, всего редактировалось 2 раз(а).
Используется синтаксис Pascal
if ( x1Re: Определить принадлежность точки отрезку.
30.07.2011, 22:23
Используется синтаксис C++
if ( ( x3 — x1 ) * ( x3 — x2 ) <= 0 ) printf ( «Принадлежит» ) ;
меньше чем одним сравнением, наверное, уже не обойтись.
Re: Определить принадлежность точки отрезку.
30.07.2011, 22:30
Переехали в «Программирование».
Re: Определить принадлежность точки отрезку.
31.07.2011, 00:12
Последний раз редактировалось PPrivett 31.07.2011, 00:15, всего редактировалось 2 раз(а).
ИСН в сообщении #472276 писал(а):
Используется синтаксис Pascal
if ( x1
Если даже не обращать внимания на то, что перепутаны x1 и x3, правая точка отрезка все равно пропадает — можно заменить на :
x1=2,
x2=1,
x3=2
(2<1)xor(2<2) будет 0(FALSE)
Re: Определить принадлежность точки отрезку.
31.07.2011, 11:38
Да, с граничными точками проблема в любом случае будет. Простейший вариант исправления:
Используется синтаксис Pascal
if ( ( x3 ( x3 then writeln ( ‘Принадлежит’ ) ;
С умножением, конечно, выглядит короче. Однако бог знает, сколько лишнего времени отнимет само умножение. Кроме того, это зависит от реализации транслятора. Статистически вариант с арифметикой менее выгоден: в нём всегда будут необходимы четыре операции, а в лигическом варианте — почти всегда три, и лшь изредка пять или семь. Можно ещё попробовать с ассемблером поковыряться, да чего-то лень.
Re: Определить принадлежность точки отрезку.
31.07.2011, 14:26
Последний раз редактировалось PPrivett 31.07.2011, 14:28, всего редактировалось 2 раз(а).
ewert в сообщении #472365 писал(а):
С умножением, конечно, выглядит короче. Однако бог знает, сколько лишнего времени отнимет само умножение.
Можно и не умножать , просто сравнить «знаки» чисел. Получается наглядно и умножения не нужно.
Используется синтаксис Pascal
if ( ( ( sgn ( x1 — x2 ) ) <> ( sgn ( x1 — x3 ) ) ) then OK
Re: Определить принадлежность точки отрезку.
31.07.2011, 14:45
PPrivett в сообщении #472397 писал(а):
Можно и не умножать , просто сравнить «знаки» чисел.
А что такое функция sgn .
Если она возвращает только значения плюс-минус единичка, то это ровно то же самое, что и использование только логических выражений. Если возвращает ещё и ноль, то всё равно будет работать неверно для отрезка нулевой длины. И в любом случае: сколько дополнительно ресурсов сожрёт обращение к этой функции.
Re: Определить принадлежность точки отрезку.
31.07.2011, 19:13
Последний раз редактировалось PPrivett 31.07.2011, 19:24, всего редактировалось 2 раз(а).
ewert в сообщении #472401 писал(а):
PPrivett в сообщении #472397 писал(а):
Можно и не умножать , просто сравнить «знаки» чисел.
А что такое функция sgn .
Если она возвращает только значения плюс-минус единичка, то это ровно то же самое, что и использование только логических выражений. Если возвращает ещё и ноль, то всё равно будет работать неверно для отрезка нулевой длины. И в любом случае: сколько дополнительно ресурсов сожрёт обращение к этой функции.
Да, с нулевым отрезком плохо вышло 🙁
sgn будет возвращать -1 0 +1, или 0 1 2 (главное чтобы 3 неравных числа). ресурсов сожрет меньше, чем умножение(реализовать можно через логические выражения,
либо используя двоичное представление числа — одно сравнение на равенство 0 и несколько битовых сдвигов. — учитывая, что первый бит знакового числа означает знак числа)
Хотя не факт, что будет работать быстрее. Для разных процессоровкомпиляторов разные результаты будут
Источник: dxdy.ru