Как оптимизировать это решение, чтобы избежать превышения лимита времени?

Question

Это мое решение этого вопроса:

Учитывая круг, представленный как (radius, x_center, y_center) и выровненный по оси прямоугольник, представленный как (x1, y1 , x2, y2), где (x1, y1) - координаты нижнего левого угла, а (x2, y2) - координаты верхнего правого угла прямоугольника.

Вернуть True, если круг и прямоугольник перекрываются, в противном случае возвращается значение False.

Другими словами, проверьте, существуют ли какие-либо точки (xi, yi), такие как принадлежащие окружности и прямоугольнику одновременно.

class Solution {
    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

        for(int i=x1; i<=x2; ){
            for(int j=y1; j<=y2; ){                
                System.out.println((Math.pow(i-x_center, 2) +" "+ Math.pow(j-y_center, 2))+" "+Math.pow(radius, 2));
                System.out.println(i+" "+j);
                if((Math.pow(i-x_center, 2)+Math.pow(j-y_center, 2))<=Math.pow(radius, 2)){
                    return true;
                }
                j += 1;
            }
            i += 1;
        }

        return false;
    }
}

Я вполне уверен, что логика c верна. Начиная от нижнего левого угла прямоугольника до верхней правой точки, для каждой точки я проверяю, находится ли она внутри круга. Если я увеличу шаг приращения до значения, превышающего «1», я вижу, что код не выполняется для тестовых случаев, когда прямоугольник и круг просто «касаются» друг друга. Но при таком способе в некоторых случаях превышение лимита времени. Как мне оптимизировать код для этой логи c?

Заранее спасибо.

Answer 1

Эта проблема может быть упрощена. Я нашел решение сложности времени O (1) и сложности памяти O (1). Вместо того, чтобы проверять каждый пиксель из прямоугольника, вы можете даже принимать во внимание только сами границы.

На мой взгляд, есть 3 случая:

1. Круг полностью внутри прямоугольника.
2. Прямоугольник полностью находится внутри круга
3. Контуры окружности и прямоугольника пересекаются как минимум в одной точке. Это сложнее.

Я назову центр координат окружности x0 и y0.

1. Вы можете просто отметить ограничивающую рамку для круга, например, которая является самой северной точкой круга (x0, y0-radius), которая является самой южной точкой круга (x0, y0 + радиус), самый восточный (x0-радиус, y0) и самый западный (x0 + радиус, y0). Если все они попадают в прямоугольник, то проблема решена.

2. Если прямоугольник полностью находится внутри круга, это определенно означает, что его углы находятся на меньшем расстоянии от центра круга чем радиус. Просто проверьте это расстояние для каждого угла.

Теперь самое сложное.

Итак, как вы выяснили, находиться в круге (или пересекается с ним) означает, что некоторая точка должна быть на меньшем или равном расстоянии от центра, чем радиус. Однако мы можем выполнить оптимизацию и для части проверки прямоугольника. Пересечение с прямоугольником, вероятно, означает пересечение хотя бы с одним из сегментов, составляющих контур прямоугольника. Итак, в случае пересечения между прямоугольником и окружностью, вам нужно проверить, есть ли какой-либо отрезок, который будет на меньшем или равном расстоянии от центра окружности, чем радиус.

Редактировать: Кроме того, причина того, что ваш код терпит неудачу в тестах, где они едва касаются, вероятно, из-за ошибок с плавающей запятой. не используйте == (или в данном случае <=, что похоже) для проверки, совпадают ли два значения с плавающей запятой (или даже с плавающей запятой и целыми числами). Math.pow () в Java возвращает значение double. Просто используйте нормальное умножение для возведения в квадрат. На самом деле, вы, возможно, захотите держаться как можно дальше от плавающей точки, если только вы не можете понять, как от них избавиться, а проблема говорит: «0.001 ошибка приемлема» или что-то в этом роде. Они оба медленные и подвержены ошибкам. </p>

Редактировать 2: Кроме того, я написал код, чтобы помочь вам понять это объяснение. Я протестировал его на сайте, он работает для каждого теста с временем выполнения 1 мс и использованием памяти 37,7 МБ.

class Solution {

    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        //case 1: circle is fully inside rectangle
        //check the bounding box of the circle against the rectangle
        if(x_center-radius>=x1&&y_center-radius>=y1
         &&x_center+radius<=x2&&y_center+radius<=y2
          )
            return true;
        //case 2: checking closest corner against circle bounds
        int minX=(Math.abs(x_center-x1)>Math.abs(x_center-x2))?(x_center-x2):(x_center-x1);
        int minY=(Math.abs(y_center-y1)>Math.abs(y_center-y2))?(y_center-y2):(y_center-y1);
        if(minX*minX+minY*minY<=radius*radius)
            return true;
        //case 3: checking distances to segments against circle bounds
        //Checking distance from a segment to a point is alike checking
        //the distance from the line the segment is part of to a point,
        //except you have to check if the closest point from the segment
        //is actually on the segment. If it isn't, the distance from a
        //segment to a point is the minimum distance from one of its
        //corners to the point.
        if(x1<=x_center&&x_center<=x2)
            if(minY*minY<=radius*radius)
                return true;
        if(y1<=y_center&&y_center<=y2)
            if(minX*minX<=radius*radius)
                return true;
        return false;
    }
}

Этот код может быть сокращен. Однако с точки зрения сложности время не может быть лучше, чем O (1).