870 - Intersecting Rectangles

[MUBBASHER]

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]

I am not quite sure about your approach..
.. 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]

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.

THANKS IN ADVANCE.
//################################
[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]

It's the only thread. Thus I post here.

Please help verify this test data:

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]

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]

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]

In this case, I think so, but in general, you would probably want to use >= instead of >

[DJWS]

EDIT:
I misunderstood the problem statement. AC now.
Thank for Darko's help.
--
DJWS, a newbie in programming

[MrBlah]

Can someone please help me undestand why im getting Presentation Error T_T? thanks in advice

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];
}

}