Calculates the extent of rectangles....

[Mortifera]

My problem is specific and brutally hard, so I'd love to, if anyone has any idea, help me:

Each rectangle, may be partially or completely covered by another rectangle. Length of border lines, union of all rectangles is called extent. Need to write a program that calculates the extent.

Input file:

Input data can be found in the file GRAPH.IN. The first line contains the number of files GRAPH.IN rectangle. In each of the next is integer (integer) coordinates of lower left and upper right top of the rectangle. The value of these coordinates are given as a decorated couples consisting of x-coordinates, followed by the value of y-coordinates.

GRAPH.IN 7
-15 0 5 10
-5 8 20 25
15 -4 24 14
-6 0 16 4
2 15 10 22
30 10 36 20
34 0 40 16

Output file:

GRAPH.OUT Output file must contain only one row with a non-negative integer that represents the requested extent of rectangles.

GRAPH.OUT 228
Time limit:

For each test case the program needs to offer a solution for more than 30 seconds.

The number of rectangles is greater than the 5000. All coordinates are from the interval [-10000.10000] and every each rectangle has a positive surface, it can not be reduced to a line or point. The numerical value of the results may require 32-bit representation (type longint or long).

The problem is that I never met with this type of problem in my life.
I have to mention that I use VisualStudio2010. Thanks!

[Duthomhas]

This looks like university homework, and it isn't that hard -- just involved.

You'll need to keep a list of non-overlapping rectangles.

Given two rectangles like this:

  ┌─────────┐  
  │         │  
  │ a   ┌───┼───┐  
  │     │ i │ b │  
  └─────┼───┘   │  
        └───────┘  

Each rectangle has an area... including the rectangle i -- which is the intersection of rectangles a and b.

I'm sure you know enough math to also know that the extent of a and b is A( a ) + A( b ) - A( i ). If you add another overlapping rectangle the formula gets more complicated. That is a lot of work, especially when you have many rectangles overlapping the same region.

Hence, it is important to keep the list a list of non-overlapping rectangles. When you add a rectangle to the list, make sure to split it up (if necessary). Our given rectangles then become something like this:

  ┌─────────┐
  │         │
  ├─────┬───┴───┐  
  │     │       │  
  └─────┤       │  
        └───────┘  

(It could have been split many different ways; Just pick one and stick to it.)

We now have three non-overlapping rectangles, and the extent is simply the sum of their areas. That's much simpler, no?

One last thing to consider: What happens if you add a rectangle that completely encompasses others?

       ┌───────┐
  ┌────┼────┐  │
  │    │    │  │
  ├────┼┬───┴──┼┐  
  │    ││      ││  
  └────┼┤      ││  
       │└──────┼┘  
       └───────┘   

Hopefully, you should adjust to this

       ┌───────┐
  ┌────┤       │
  │    │       │
  ├────┤       ├┐  
  │    │       ││  
  └────┤       ││  
       │       ├┘  
       └───────┘   

These two operations are actually one and the same: first split and add, second prune. (This is easy if you do it for every rectangle you add -- since you know which rectangle has to encompass others to do pruning.


As far as I can see, your assignment doesn't require you to actually draw anything to the console, just print the total extent of your rectangles.

Hope this helps.

[m4ster r0shi]

This looks more like a competition to me.

Are non-deterministic ways out of the question? You could use that monte-carlo thing:

-> Find the left-most and right-most x coordinates, X_L, X_R and
the top-most and bottom-most y coordinates, Y_T, Y_B.
Let's call A the rectangle formed by (X_L,Y_T) and (X_R,Y_B).

-> Sort your rectangles depending on their extent in descending order
(this is supposed to make the following steps faster,
but if you see that sorting takes too much time don't do it)

-> Get a random number X between X_L and X_R
and another random number Y between Y_T and Y_B.
Check if the point (X,Y) is inside any of your rectangles.

-> Repeat the above many times keeping track of the total number of test points,
TOTAL, and the number of test points that are inside your rectangles, INSIDE.

->Then, the required extent is given by (INSIDE/TOTAL)*extent(A)
(assuming you use a good random number generator and TOTAL is quite big)

EDIT: (after seeing ne555's post below)

Lol... Well, if anyone wants a fast, probabilistic way to calculate the area, it's here!

[ne555]

Length of border lines, union of all rectangles is called extent

Perimeter (no area)
Sort the retangles by x, then y. (it will make the interseciton computation easier)

[Mortifera]

I know the Monte Carlo test, but I've never made anything like that. The problem is SOLVING on that way. That task is just too heavy, so again I did not understand. I don't have that big experience like you two guys, to solve this problem.

[m4ster r0shi]

What do you mean when you say extent? Is it the perimeter or the area?
The monte-carlo method is used to calculate the area. If you want the perimeter it's useless.

[Mortifera]

m4ster r0shi, and rest of pplz I mean something like this

http://img830.imageshack.us/img830/56/53952386.jpg

The red line is that, what I have to calculate.

[quirkyusername]

you still haven't really explained what you need, is it the length of the red line or the area within it?

[Duthomhas]

Oops! I misread that you wanted the area extent, but you want the perimeter extent.

In that case you are better off keeping a list of shapes which are themselves lists of points defining an area. When you add a new rectangle, perform the proper pruning and/or joining. When you are done, simply sum all the segments together.

If this is a competition, that's about all the help you'll get -- the point is to figure it out yourself.

[ne555]

A similar problem that might help you.
Compute the borderline of the Andes. Assume that all the mountains are [isosceles] right triangles, supported on the hypotenuse.
(hint: sort)

Edit: isosceles right triangles

[Mortifera]

@Duoas, it is not competition, because I don't have so much experience like you and rest of pplz...My field of expertise is database (MySQL, FoxPro...).
@quirkyusername - lenght of the red line

[Mortifera]

I know to calculate area within red line:

#include<iostream>
using namespace std;

bool matrica[5001][5001];

void main(){

	int i,j,k;

	int n, x1,x2,y1,y2,res=0;
	cout<<"Input number";
	cin>>n;
	cout<<endl;
	for(i=0;i<n;i++)
	{
		cin>>x1;
		cin>>x2;
		cin>>y1;
		cin>>y2;
		for(j=x1;j<x2;j++)
			for(k=y2;k<y1;k++)
				if( matrica[j][k] == false )
					matrica[j][k]=true,res++;
	}

	cout<<" Result is: "<<res<<endl;
}

Coordinate is formed like: x1,x2,y1,y2, where (x1,y1) it top left and (x2,y2) is a lower right.
All this process takes place in a positive part of the XY coordinates.

[ne555]

Except that it is very inefficient

All coordinates are from the interval [-10000.10000]

Your matrix should be 20001x20001

[Mortifera]

Yes, but if I put the matrix as much as you already stated, then the problem happens with the input with negative numbers, the program simply crashes.

[ne555]

Use a linear transform x' = a*x + b
0 -> -10000
20000 -> 10000

[Mortifera]

#include <iostream>
#include<fstream>
#include<sstream>
#include<stdio.h>
using namespace std;

bool mat[10005][10005];

int d[][2] = { {1,0} , {-1,0} , {0,-1} , {0,1} };

int main()
{
	
	int i,j,k;
	int n, x1,x2,y1,y2;
	ifstream Input("GRAPH.IN");
	if (!Ulaz)
	{
		cout<<" Could not open input file! "<<endl;
		exit(-1);
	}
	ofstream Output("GRAPH.OUT");
	if (Izlaz.fail())
	{
		cout<<" Could not open output file!"<<endl;
		exit(-1);
	}
	if (n>=5000)
	{
		cout<<"The number of elements is greater than anticipated! "<<endl;
		return 0;
	}
	for(i=0;i<n;i++)
	{
		Input>>x1;
		Input>>y1;
		Input>>x2;
		Input>>y2;
		x1 += 500 , x2 += 500 , y1 += 500 , y2 += 500;
		for(j=x1;j<x2;j++)
			for(k=y1;k<y2;k++)
				mat[j][k]=true;
	}
	int sol = 0;
	for( int r = 0; r <= 10000; ++r )
	{
		for( int c = 0; c <= 10000; ++c )
		{
			if( mat[r][c] == false ) 
				continue;
			for( int k = 0; k < 4; ++k )
			{
				int nr = r + d[k][0];
				int nc = c + d[k][1];
				if( nr < 0 || nc < 0 || mat[nr][nc] == false ) sol ++;
			}
		}
	}
	Output<<sol;
	return 0;
}

After many hours spent in front of the monitor, I found and implemented solutions. Now the program can read both positive and negative values of numbers. Basically, the program does exactly what it should to do. Thanks for supporting me, and I hope that this program code will help to someone! Thanks guys, you are really nice!