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.
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();
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…