Geek asks and answers

Calculate the perimeter and area of ​​intersecting rectangles?

I searched a lot, but I did not find a good answer that works for this case. We have rectangles, horizontal or vertical. They can be placed on the page at random. They can overlap or have a common edge or be separated from each other. I want to find an algorithm with O (nlogn) that can find the perimeter and area of ​​these rectangles. These pictures can make the problem understandable.

enter image description here

I think interval trees can help, but I'm not sure how to do this.

+5
source share
2 answers

This can be done using a sweep algorithm.

. , , .

, x x1 x2. , x1 L, , (x2 - x1) * L, x1 x2.

, x1 , x1 ( :)): enter image description here

, . .

:

insert_interval(y1, y2); 
get_total_length();

, .

:

  • x.
  • x ( , ):
    • x1 - x.
    • x2 - x.
    • L - , .
    • (x2 - x1) * L .
    • x = x2 .
    • x = x2 .

.

, , . x.

- O (N log N) ( , , ).

TopCoder.

PEG wiki.

( ) SPOJ NKMARS: .

+8

O (N2).

int area = 0;
FOR(triange=0->N)
{
    Area = area trianlges[triangle];
    FOR(int j = triangle+1 -> N)
    {
        area-= inter(triangle , j)
    }
}
return area;

int inter(tri a,tri b)
{
    if ( ( min(a.highY ,b.highY) > max(a.lowerY, b.lowerY) ) && ( min(a.highX ,b.highX) > max(a.lowerX, b.lowerX) ) )
    return ( min(a.highY ,b.highY) - max(a.lowerY, b.lowerY) ) * ( min(a.highX ,b.highX) - max(a.lowerX, b.lowerX) )

    else return 0;
}
0

More articles:


All Articles