### 11345 - Rectangles

Posted:

**Mon Nov 12, 2007 7:40 am**Why WA.........

Code: Select all

```
Cut after AC.....
```

The UVa Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=41&t=24859

Page **1** of **2**

Posted: **Mon Nov 12, 2007 7:40 am**

Why WA.........

Code: Select all

```
Cut after AC.....
```

Posted: **Mon Nov 12, 2007 8:32 am**

Try this.

**INPUT:**
**OUTPUT:**
ADD : If you meet these kind of problems, try everything. Finding the trick is also the part of the problem.

----

Rio

Code: Select all

```
1
2
0 0 1 1
1 1 0 0
```

Code: Select all

```
Case 1: 0
```

----

Rio

Posted: **Tue Nov 13, 2007 7:32 pm**

Are you sure? I think the answer is 1 not 0. because two rectangles are the same.rio wrote:Try this.

INPUT:Code: Select all

`1 2 0 0 1 1 1 1 0 0`

OUTPUT:ADD : If you meet these kind of problems, try everything. Finding the trick is also the part of the problem.Code: Select all

`Case 1: 0`

----

Rio

Posted: **Tue Nov 13, 2007 8:23 pm**

Is there any tricky IO?

Posted: **Tue Nov 13, 2007 11:05 pm**

All I did was to find the maximum x1, minimum x2, maximum y1 and minimum y2 over all input.saman_saadi wrote:Is there any tricky IO?

As a side effect, if x2<=x1 or y2<=y1 in any rectangle, the answer is 0

Posted: **Wed Nov 14, 2007 8:28 pm**

Thanks sclo for your quick reply. Your method is much better than mine and it works correctly but I don't know why my method is wrong. My algorithms is:sclo wrote:All I did was to find the maximum x1, minimum x2, maximum y1 and minimum y2 over all input.saman_saadi wrote:Is there any tricky IO?

As a side effect, if x2<=x1 or y2<=y1 in any rectangle, the answer is 0

I use a priority queue that the rectangle with smallest x1 exit first. I push all input rectangles into priority queue. Suppose r1 and r2 be the first and the second rectangle that we pop from the priority queue:

the answer is 0 if (r2.x1 >= r1.x2 or (r2.y1 >= r1.y2 or r2.y2 <= r1.y1)) otherwise we make a new rectangle that we call r:

r.x1 = r2.x1

r.y1 = max(r1.y1, r2.y1)

r.x2 = min(r1.x2, r2.x2)

r.y2 = min(r1.y2, r2.y2)

then we push r into priority queue.we repeat above algorithm until the priority queue size is equal to one or we found the answer is 0.

Posted: **Wed Nov 14, 2007 11:16 pm**

what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm?

Posted: **Thu Nov 15, 2007 5:34 pm**

I think I handle all of these:sclo wrote:what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm?

1) r.x1 > r.x2 => r2.x1 > min(r1.x2, r2.x2)

we know r2.x1 < r2.x2 so we must have r1.x2 < r2.x1 that I handle this.

2) r.y1 > r.y2 => max(r1.y1, r2.y1) > min(r1.y2, r2.y2)

suppose that min(r1.y2, r2.y2) = r1.y2:

r1.y2 < max(r1.y1, r2.y1) => r1.y2 < r2.y1 that I handle this

now suppose min(r1.y2, r2.y2) = r2.y2:

r2.y2 < max(r1.y1, r2.y1) => r2.y2 < r1.y1 that I handle this.

So I handle all cases that you consider.

Posted: **Thu Nov 15, 2007 7:46 pm**

Obviously, something is wrong with your logic somewhere. But I don't really see it.saman_saadi wrote:I think I handle all of these:sclo wrote:what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm?

1) r.x1 > r.x2 => r2.x1 > min(r1.x2, r2.x2)

we know r2.x1 < r2.x2 so we must have r1.x2 < r2.x1 that I handle this.

2) r.y1 > r.y2 => max(r1.y1, r2.y1) > min(r1.y2, r2.y2)

suppose that min(r1.y2, r2.y2) = r1.y2:

r1.y2 < max(r1.y1, r2.y1) => r1.y2 < r2.y1 that I handle this

now suppose min(r1.y2, r2.y2) = r2.y2:

r2.y2 < max(r1.y1, r2.y1) => r2.y2 < r1.y1 that I handle this.

So I handle all cases that you consider.

Posted: **Tue Nov 27, 2007 7:39 pm**

what's wrong? why WA?
any more I/O

Code: Select all

`code removed`

Posted: **Wed Nov 28, 2007 4:16 pm**

if(t.x2>=t.x1&&t.y2>=t.y1)

area = ( t.x2 - t.x1 ) * ( t.y2 - t.y1 ) ;

else

area = 0 ;

hope it help.

and cut this->

if( r*.x2 <= t.x1 || t.x2 <= r**.x1 || r**.y2 <= t.y1 || t.y2 <= r**.y1 ) *

{

area = 0 ; break ;

}

area = ( t.x2 - t.x1 ) * ( t.y2 - t.y1 ) ;

else

area = 0 ;

hope it help.

and cut this->

if( r

{

area = 0 ; break ;

}

Posted: **Thu Nov 29, 2007 8:26 pm**

again WA

Posted: **Thu Nov 29, 2007 9:03 pm**

How did you fixed your code ?Masud_CSE_SUST wrote:again WA

Update your code, or erase it and post a new one.

-----

Rio

Posted: **Fri Nov 30, 2007 11:36 am**

Updated code (got WA)How did you fixed your code ?

Update your code, or erase it and post a new one.

Code: Select all

```
#include <stdio.h>
struct ractangle
{
int x1, y1, x2, y2 ;
} ;
int main ()
{
//freopen( "11345.in", "r", stdin ) ;
int T, kase, i, N, area ;
ractangle r[50], t ;
scanf( "%d", &T ) ;
kase = 1 ;
while( T-- )
{
scanf( "%d", &N ) ;
for( i = 1; i<= N; i++ )
{
scanf( "%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2 ) ;
if( r[i].x1 >= r[i].x2 || r[i].y1 >= r[i].y2 )
{
area = 0 ; goto end ;
}
}
t = r[1] ;
for( i = 2; i <= N; i++ )
{
/*if( r[i].x2 <= t.x1 || t.x2 <= r[i].x1 || r[i].y2 <= t.y1 || t.y2 <= r[i].y1 )
{
area = 0 ; break ;
}*/
t.x1 = r[i].x1 > t.x1 ? r[i].x1 : t.x1 ;
t.x2 = r[i].x2 < t.x2 ? r[i].x2 : t.x2 ;
t.y1 = r[i].y1 > t.y1 ? r[i].y1 : t.y1 ;
t.y2 = r[i].y2 < t.y2 ? r[i].y2 : t.y2 ;
if( t.x2 >= t.x1 && t.y2 >= t.x1 )
area = ( t.x2 - t.x1 ) * ( t.y2 - t.y1 ) ;
else { area = 0 ; break ; }
}
end : ;
printf( "Case %d: %d\n", kase++, area ) ;
}
return 0 ;
}
```

Posted: **Fri Nov 30, 2007 3:03 pm**