主页 / 问题 / 927299
Accepted
Dr. kott9ra
Asked:2020-12-31 21:24:24 +0000 UTC2020-12-31 21:24:24 +0000 UTC

点是否属于线段的问题

  • 772

有一个任务：

第一行包含两个整数 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 3 3 时给出 0 3 5 5 1 1。我想知道我的算法中的错误在哪里。如果是的话，请把我推向正确的解决方案:)

    导入 java.io.BufferedReader；导入 java.io.IOException；导入 java.io.InputStreamReader；导入 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];
        List<Segment> segments = 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] && segment.y >= 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;
        }
    }
}
java

2 个回答

  1. Best Answer

    接下来，我们看，如果该点不属于任何段，但属于至少一个段，那么它也不属于所有后续段。（因为这些段是按初始坐标的升序排列的）。

    这不是真的。假设我们有 segment [0 100] [10 20] [40 80]。它们按原产地排序。该点50属于第一段，不属于第二段。由此你得出一个奇怪的结论，“它也不属于所有后续的”。但是这是错误的。她属于[40 80]。

    即使正确实施，您的方法也会非常低效，因为它会为每个点搜索整个段数组。对段数组进行排序的事实允许您根据条件检查提前结束搜索segment.x > dots[i]，但这并没有什么不同。平均而言，您必须检查每个点的一半。

    您正在尝试实现在线算法，即 一种独立于其他点处理每个点的算法。在任务下线的情况下明确告知你不需要这样做，即 所有测试点都是预先知道的。离线解决方案总是比在线解决方案更有效（或者，出于显而易见的原因，不会比它更差）。

    如果任务是构建一个在线解决方案，那么一种有效的方法就是构建一个像线段树这样的经典数据结构。通过对细分进行排序，您实际上是朝着这个方向迈出了一步。但是，再一次，在您的问题陈述的框架内，为此付出努力是没有意义的。

    该问题的有效离线解决方案可以基于合并两个排序数组的经典原理。两个数组——段和点——都必须提前排序，然后通过两个数组的同步传递，得到问题的答案。该算法的结构也类似于一维版本的扫描线算法（它支持许多“活动”段）。

    例如，在 C++ 中

    #include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <iostream>

int main()
{
  unsigned n, m;
  std::cin >> n >> m;

  using Segment = std::pair<int, int>;
  std::vector<Segment> segments(n);
  for (Segment &segment : segments)
    std::cin >> segment.first >> segment.second;

  std::vector<int> points(m);
  std::vector<unsigned> counts(m);
  for (int &point : points)
    std::cin >> point;

  // Сортируем отрезки по началам
  std::sort(segments.begin(), segments.end());

  // Сортируем точки (через индексный массив)
  std::vector<unsigned> point_index(m);
  std::iota(point_index.begin(), point_index.end(), 0u);
  std::sort(point_index.begin(), point_index.end(), 
    [&](unsigned li, unsigned ri) { return points[li] < points[ri]; });

  // Заводим список активных отрезков - упорядочен по концам отрезков
  auto cmp_second = 
    [](const Segment *lhs, const Segment *rhs) { return lhs->second < rhs->second; };
  std::multiset<const Segment *, decltype(cmp_second)> 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 <= point; ++it_segment)
      if (it_segment->second >= point)
        active_segments.insert(&*it_segment);

    // Ответ для текущей точки - количество активных отрезков
    counts[i_point] = active_segments.size();
  }

  for (unsigned count : counts)
    std::cout << count << " ";

  std::cout << std::endl;
}

    http://coliru.stacked-crooked.com/a/f37d52223571f42d

    顺便说一句，您输入的正确答案0 3 5 5 4 3是，不是0 3 5 5 3 3。

    • 3

  2. 删除所有与dotsB[i]. 逻辑

    } else {
  if (dotsB[i]) { 
    break; 
  }
}

    错误的。

    • 1

相关问题