Задача
Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).
Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].
Входные данные
[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]
Выходные данные
[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].
Тест
| Входные данные | Выходные данные |
|---|---|
| 20 11
14 4 |
1 6 9 9 11 12 12 12 13 15 15 |
Иллюстрация к тесту:
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
import java.util.*; import java.lang.*; import java.io.*; class Dot { public double x, y; public Dot() {} public Dot(double x, double y) { this.x = x; this.y = y; } } public class Main { public static double euclidianDistanceToZero(Dot a) { return Math.sqrt(a.x*a.x+a.y*a.y); } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int n_dot = in.nextInt(); int n_circ = in.nextInt(); Vector <Dot> dots = new Vector<Dot>(); for(int i = 0; i < n_dot; ++i) { Dot a = new Dot(in.nextDouble(), in.nextDouble()); if (a.y > 0) dots.addElement(a); } double rads[] = new double[n_circ]; int amounts[] = new int[n_circ]; for(int i = 0; i < n_circ; ++i) { rads[i] = in.nextDouble(); amounts[i] = 0; } if (n_circ == 1) { for(int i = 0; i < dots.size(); ++i) if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0]) ++amounts[0]; } else for(int i = 0; i < dots.size(); ++i) { int j = n_circ; double r = euclidianDistanceToZero(dots.elementAt(i)); if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles { if (r < rads[0]) // if dot belongs to the first semicircle j = 0; else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle j = n_circ-1; else // binary search of the smallest semicircle, which includes dot { int prev_l = 0, prev_r = n_circ, k; while(j == n_circ) { k = (prev_l+prev_r)/2; if (rads[k-1] <= r && r < rads[k]) j = k; else if (r >= rads[k]) prev_l = (prev_l+k)/2; else //if (r < rads[k-1]) prev_r = (prev_r+k)/2; } } ++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles. } } for(int accumulated_amount = 0, i = 0; i < n_circ; ++i) { accumulated_amount += amounts[i]; amounts[i] = accumulated_amount; } for(int i = 0; i < n_circ; ++i) out.println(String.valueOf(amounts[i])); out.flush(); } } |
Решение задачи
Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.
После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.
Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.
Ссылки
- Код на ideone.com;
- Условие задачи, страница 126.