11345 - Rectangles

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

11345 - Rectangles

Post by shakil » Mon Nov 12, 2007 7:40 am

Why WA.........

Code: Select all

Cut after AC.....
Last edited by shakil on Mon Nov 12, 2007 9:12 am, edited 1 time in total.
SHAKIL

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Nov 12, 2007 8:32 am

Try this.
INPUT:

Code: Select all

1
2
0 0 1 1
1 1 0 0
OUTPUT:

Code: Select all

Case 1: 0
ADD : If you meet these kind of problems, try everything. Finding the trick is also the part of the problem.
----
Rio

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Tue Nov 13, 2007 7:32 pm

rio wrote:Try this.
INPUT:

Code: Select all

1
2
0 0 1 1
1 1 0 0
OUTPUT:

Code: Select all

Case 1: 0
ADD : If you meet these kind of problems, try everything. Finding the trick is also the part of the problem.
----
Rio
Are you sure? I think the answer is 1 not 0. because two rectangles are the same.

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Tue Nov 13, 2007 8:23 pm

Is there any tricky IO?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Nov 13, 2007 11:05 pm

saman_saadi wrote:Is there any tricky IO?
All I did was to find the maximum x1, minimum x2, maximum y1 and minimum y2 over all input.
As a side effect, if x2<=x1 or y2<=y1 in any rectangle, the answer is 0

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Wed Nov 14, 2007 8:28 pm

sclo wrote:
saman_saadi wrote:Is there any tricky IO?
All I did was to find the maximum x1, minimum x2, maximum y1 and minimum y2 over all input.
As a side effect, if x2<=x1 or y2<=y1 in any rectangle, the answer is 0
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:

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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Nov 14, 2007 11:16 pm

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

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Thu Nov 15, 2007 5:34 pm

sclo wrote:what happens when r.x1>r.x2 or r.y1>r.y2 in your algorithm?
I think I handle all of these:
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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Nov 15, 2007 7:46 pm

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

User avatar
Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Location: Sylhet, Bagladesh
Contact:

Post by Masud_CSE_SUST » Tue Nov 27, 2007 7:39 pm

what's wrong? why WA?

Code: Select all

code removed
any more I/O
Last edited by Masud_CSE_SUST on Fri Nov 30, 2007 11:35 am, edited 2 times in total.
"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » 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 ;
}
SHAKIL

User avatar
Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Location: Sylhet, Bagladesh
Contact:

Post by Masud_CSE_SUST » Thu Nov 29, 2007 8:26 pm

again WA
"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Nov 29, 2007 9:03 pm

Masud_CSE_SUST wrote:again WA
How did you fixed your code ?
Update your code, or erase it and post a new one.

-----
Rio

User avatar
Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Location: Sylhet, Bagladesh
Contact:

Post by Masud_CSE_SUST » Fri Nov 30, 2007 11:36 am

rio wrote
How did you fixed your code ?
Update your code, or erase it and post a new one.
Updated code (got WA)

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 ;
}
"Computer science is no more about computers than astronomy is about telescopes." - Dijkstra

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Nov 30, 2007 3:03 pm

Try this.
Input:

Code: Select all

2
2
1 1 0 0
0 0 1 1
1
0 0 1 1
-----
Rio

Post Reply

Return to “Volume 113 (11300-11399)”