我的 N 的矩形与边平行于x轴和y轴。还有另外一个矩形，模式的。我需要创建一个算法，它可以告诉有无的模式的被完全覆盖的 N 的矩形。

I have N rectangles with sides parallel to the x- and y-axes. There is another rectangle, model. I need to create an algorithm that can tell whether the model is completely covered by the N rectangles.

我有一些想法。我认为，首先，我需要在矩形他们的左侧进行排序（它可以在完成为O（n log n）的的时间），然后用一个垂直扫线。

I have some ideas. I think that first, I need to sort the rectangles by their left side (it can be done in O(n log n) time), and then use a vertical sweeping line.

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

蓝色矩形是的模式的。

首先，我需要抽象的算法。没有特殊的要求方面的实现。的矩形可以重新psented为一对点（左上和右下）。

First of all, I need the abstract algorithm. There are no special requirements with regard to the realization. A rectangle can be represented as a pair of points (left-top and bottom-right).

这是为preparing用于测试的任务之一。我知道最好的算法可以在 0做到这一点（N日志N）的时间。

This is one of the tasks for preparing for a test. I know that the best algorithm can do this in O(n log n) time.

推荐答案

下面是一个分而治之算法。一般案件的复杂性是非常好的，我会说这是类似 O（N日志MaxCoords）。最坏的情况可能是二次不过，但是我认为这样的测试是pretty的难以形成。为了使它更难，做递归函数的调用顺序是随机的。也许什么@Larry建议能得到这个为O（n log n）的的平均水平。

Here's a divide and conquer algorithm. AVERAGE case complexity is very good and I'd say it's something like O(n log MaxCoords). Worst case could be quadratic though, however I think such a test would be pretty difficult to create. To make it even harder, make the order of the recursive function calls random. Maybe what @Larry suggested can get this to O(n log n) on average.

我想不出一个扫线的解决方案，但对于测试我已经试过这是非常快的。

I can't figure out a sweep line solution, but for the tests I've tried this is very fast.

基本上，使用递归函数上蓝色矩形的作品。首先检查蓝色的矩形完全覆盖其他矩形之一。如果是的话，我们就大功告成了。如果不是，将它分成4个象限，并递归地呼吁那些象限的功能。所有4递归调用必须返回true。我包括一些C＃code绘制的矩形。你可以改变它具有较大的值，以工作为好，但不要删除绘图程序，在这种情况下，因为这些将永远。我已经用一百万矩形和侧面的方检验之一十亿生成，使得它不是盖的，和所提供的答案（假）历时约一个第二上一个四核。

Basically, use a recursive function the works on the blue rectangle. First check if the blue rectangle is completely covered by one of the other rectangles. If yes, we're done. If not, split it into 4 quadrants, and recursively call the function on those quadrants. All 4 recursive calls must return true. I'm including some C# code that draws the rectangles. You can change it to work with larger values as well, but do remove the drawing procedures in that case, as those will take forever. I've tests it with a million rectangles and a square of side one billion generated such that it isn't covered, and the provided answer (false) took about a second on a quadcore.

我测试过这个随机的数据居多，但它似乎是正确的。如果事实证明它是不是我就删除，但也许它会得到你在正确的道路上。

I've tested this on random data mostly, but it seems correct. If it turns out it isn't I'll just delete this, but maybe it'll get you on the right path.

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }