## 870 - Intersecting Rectangles

Moderator: Board moderators

MUBBASHER
New poster
Posts: 10
Joined: Mon Oct 04, 2004 5:23 am

### 870 - Intersecting Rectangles

I have solved 870 ( Intersecting Rectangles )
Problem, But Why WA?

I have used floodfill to calculate intersection area.

Then i have grouped those rectangles which have connection with the main Rectangle.

Calculated there total area.Then subtracted Total Intersection area from it.

Can somebody tell some wrong with this approach.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
.. but my method is a bit different..

-- first i flagged all the rectangles that are connected to the main one directly/indirectly using dfs()
-- then I pushed all the x-coordintes of all the flagged rectangles into an array and sorted them
-- then I did the same thing with the y-coordinates.
-- then I simply added the areas of the rectangles that fall within the consecutive x and y coordinates.

And you said you used floodfill to mark the areas.. how do you know the upper limit of the cooordinates..

MUBBASHER
New poster
Posts: 10
Joined: Mon Oct 04, 2004 5:23 am
Yes The UPPER LIMIT IS i know from a friend who solved it is 30 X 30

in your message you talk about DFS() what does it mean ? what does it do ?

Here is My code: Can You Tell me What is wrong with it or test Case Where It Fails.

//################################
[cpp]
#include<iostream>
using namespace std;
#include<math.h>

class rect
{
public:
rect()
{
sx=sy=ex=ey=nArea=0l;
}
float sx,sy,ex,ey;
float nArea;
};

bool Exists(rect *A[],int length,rect * o)
{
for(int i=0;i<length;i++)
{
if(A==o)
return true;
}
return false;
}

void main(void)
{

int n;

cin>>n;

long * area = new long[n];

for(int i=0;i<n;i++)
{

int t=0;
cin>>t;

char table[100][100]={0};

rect * objs = new rect[t];
rect * A[100]={0};

for(int os=0;os<t;os++)
{
cin>>objs[os].sx;
cin>>objs[os].sy;
cin>>objs[os].ex;
cin>>objs[os].ey;

/*
int lx =objs[os].ex - objs[os].sx;
int ly =objs[os].ey - objs[os].sy;

for(int fx=0;fx<lx;fx++)
{
for(int fy=0;fy<ly;fy++)
{
if( table[ int(objs[os].sx+fx) ] [ int(objs[os].sy+fy) ]=='1')
{
objs[os].nArea++;
}
else
table[ int(objs[os].sx+fx) ][ int(objs[os].sy+fy) ]='1';
//table[fx][fy]='1';
}
}
*/

}

A[0]=&objs[0];
int cakes=0;
for(int nCount=0;nCount<100 && A[nCount]!=0;nCount++)
{
for(int sa=0;sa<t;sa++)
{
if(A[nCount]!=&objs[sa])
{
if(!Exists(A,cakes,&objs[sa]))
{
float sdx = ( (A[nCount]->ex-A[nCount]->sx)/2.0f ) + ( (objs[sa].ex-objs[sa].sx)/2.0f ) ;
float sdy = ( (A[nCount]->ey-A[nCount]->sy)/2.0f ) + ( (objs[sa].ey-objs[sa].sy)/2.0f );

float cdx = ( (A[nCount]->sx+A[nCount]->ex)/2.0f ) - ( (objs[sa].sx+objs[sa].ex)/2.0f );
float cdy = ( (A[nCount]->sy+A[nCount]->ey)/2.0f ) - ( (objs[sa].sy+objs[sa].ey)/2.0f );

cdx = (cdx>=0)?cdx:(-1*cdx);
cdy = (cdy>=0)?cdy:(-1*cdy);

if( (cdx<sdx && cdy<sdy) )
{
A[++cakes] = &objs[sa];
}
}

}
}
}

for(int q=0;q<=cakes;q++)
{
int lx =A[q]->ex - A[q]->sx;
int ly =A[q]->ey - A[q]->sy;

for(int fx=0;fx<lx;fx++)
{
for(int fy=0;fy<ly;fy++)
{
if( table[ int(A[q]->sx+fx) ] [ int(A[q]->sy+fy) ]=='1')
{
A[q]->nArea++;
}
else
table[ int(A[q]->sx+fx) ][ int(A[q]->sy+fy) ]='1';
//table[fx][fy]='1';
}
}
}

long sum=0l,nAREA=0l;

for(int tot=0;tot<=cakes;tot++)
{
if(A[0]->nArea==0)
{
sum=0;
nAREA=0;
break;
}
nAREA = nAREA + A[tot]->nArea;
sum = sum + (A[tot]->ex-A[tot]->sx)*(A[tot]->ey-A[tot]->sy);
}

area=sum-nAREA;

//if(i!=0)
// cout<<"\n";
//cout<<"\n"<<area<<"\n";

}

for(int j = 0;j<n;j++)
{
if(j!=0)
cout<<"\n\n";

cout<<area[j];
}

}

//########################################[/cpp]

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
It's the only thread. Thus I post here.

Code: Select all

``````2
2
1 1 2 2
2 2 3 3
2
1 2 2 3
2 1 5 4``````
Thanks a lot!
--
DJWS, a newbie in programming

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I got

Code: Select all

``````1

10
``````
But that input is invalid:
as a simplification, it can be considered that no coincidences between edges and vertices exist

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
I have no idea why getting WA.

Is it right?

Code: Select all

``````friend bool intersect(const Rect& r1, const Rect& r2) {
if (r1.x1 > r2.x2 || r2.x1 > r1.x2) return false;
if (r1.y1 > r2.y2 || r2.y1 > r1.y2) return false;
return true;
}``````
--
DJWS, a newbie in programming

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
In this case, I think so, but in general, you would probably want to use >= instead of >

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
EDIT:
I misunderstood the problem statement. AC now.
Thank for Darko's help.
--
DJWS, a newbie in programming

MrBlah
New poster
Posts: 2
Joined: Tue May 15, 2007 4:18 am
Location: Shilito

Code:
#include <cstdlib>
#include <iostream>

using namespace std;

int Xi[100],Yi[100],Xf[100],Yf[100],N,xim=30000,yim=30000,xfm=0,yfm=0,R[1000];
bool Rango[100],A[100][100];

void Func(int i){
int j,k,l,m,n,o,p;
for(l=0;l<N;l++){
if(Rango[l]==true){
for(j=Xi[l];j<=Xf[l];j++){
for(p=Xi;p<=Xf;p++)
if(p==j){
for(k=Yi[l];k<=Yf[l];k++){
for(o=Yi;o<=Yf;o++)
if(o==k){
Rango=true;
if(Xf[l]==Xi && Yf[l]==Yi){}
else{
for(m=Xi+1;m<=Xf;m++)
for(n=Yi+1;n<=Yf[i];n++)A[m][n]=true;
}
if(Xi[i]<xim)xim=Xi[i];
if(Yi[i]<yim)yim=Yi[i];
if(Xf[i]>xfm)xfm=Xf[i];
if(Yf[i]>yfm)yfm=Yf[i];
return;
}
}
}
}
}
}
}

int Area(){
int i,j,k,Area=0;
for(i=xim;i<=xfm;i++)
for(j=yim;j<=yfm;j++)
if(A[i][j]==true)Area++;

return Area;
}

int main(){
int i,j,C,k=0;

cin>>C;
cout<<"\n";
while(k!=C){
cin>>N;
cin>>Xi[0]>>Yi[0]>>Xf[0]>>Yf[0];
for(i=0;i<100;i++){
Rango[i]=false;
for(j=0;j<100;j++)A[i][j]=false;
}
Rango[0]=true;
for(i=1;i<N;i++)cin>>Xi[i]>>Yi[i]>>Xf[i]>>Yf[i];
for(i=0;i<N;i++)for(j=0;j<N;j++)Func(j);
R[k]=Area();
k++;
if(k!=C)cout<<"\n";
}
for(k=0;k<C;k++){
if(k!=0)cout<<"\n\n";
cout<<R[k];
}

}
ARG!