10574  Counting Rectangles
Moderator: Board moderators

 New poster
 Posts: 13
 Joined: Tue Jul 22, 2003 1:57 pm
 Location: Kavadarci, Macedonia
 Contact:
10574  Counting Rectangles
Hi.
Can someone give me any hint how to solve this problem without receiving TIME LIMIT EXCEEDED?
I tried to sort the points (C++ QUICK SORT), first by X and then by Y coordinate, and after that run 4 for loops with breaking conditions.
Is this slow?
Can someone give me any hint how to solve this problem without receiving TIME LIMIT EXCEEDED?
I tried to sort the points (C++ QUICK SORT), first by X and then by Y coordinate, and after that run 4 for loops with breaking conditions.
Is this slow?

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
That's definitely too slow. You're running a O(n^4) algorithm down here. That'll be 5000^4 = 625e12. Include another factor of 10 for the test cases and you have this super big number!
An idea that I have (which might not work) is to sort first, then use 2 for loops to run through every two points. These two points will be the opposite corners of the square (if they exist). Then search through a hash table to see if the other 2 points exist as well.
I'll try coding that when I'm free... busy with studies lately...
Good luck!
An idea that I have (which might not work) is to sort first, then use 2 for loops to run through every two points. These two points will be the opposite corners of the square (if they exist). Then search through a hash table to see if the other 2 points exist as well.
I'll try coding that when I'm free... busy with studies lately...
Good luck!
I think this is not the only thing to do, as you may have rectangles instead of squares....
So, my idea is:
Of course this can be reduced. Once you got i and i1, search for i2 only on points with y == Y and x > X. Note that we must have Y != Y[i1]. The search for the final point can be done on points with x == X[i2].
This will require a sort on Y also, to help the search for i2.
I don't know if this is the best way to solve this one, but I think it should solve it. I'll try to implement it when I have some free time.
JP.
So, my idea is:
Code: Select all
01. sort on X
02. for i = 1 to num_points  3 do
03. i1 = i + 1
04. while X[i1] == X[i] // Here we have one side of the rectangle
05. i2 = i1 + 1
06. while X[i2] == X[i] do
07. i2 = i2 + 1
08. while i2 < num_points  1 do
09. if Y[i2] == Y[i] // the third point was found
10. if find point with x = X[i2] and y = Y[i1]
11. increase total
This will require a sort on Y also, to help the search for i2.
I don't know if this is the best way to solve this one, but I think it should solve it. I'll try to implement it when I have some free time.
JP.
We have implemented O(N^2) algorithm during the contest (even if the complexity analysis is a bit tricky ). Idea is as follows: Sort the points by their xcoordinate. If the points have equal xcoordinate, sort them by y. So we have some sequences of points with xcoordinates x_1<x_2<...<x_k. For every i=1..k we compute, where in the array the points with given xcoodrinate x_i begin and end. Now we go through every pair of xcoordinates x_i, x_j, x_i<x_j and compute, how many rectangles there are with left edge on x_i and right edge on x_j. Since we have fixed xcoordinate, the only thing we can choose is ycoordinates of top and bottom edge. We have to have 2 points with the same ycoordinate and xcoordinates x_i and x_j and another 2 points with same ycoordinate. Since have sorted ycoordinates of points with xcoordinate x_i and x_j, we go through these 2 arrays (one for x_i and second for x_j) and find points with same ycorrdinate (something similiar to merge in mergesort). (We are formally doing an intersection of a sets of ycoordinates of that points) We can compute this in time O(k+l) where k and l are lenghts of that array. So we know possible ycoordinates (let p be the number of that ycoordinates) for top and bottom edges, how many rectangles there are? Trivial combinatorics says, that here are exactly (p*(p1))/2 rectangles.
To the complexity analysis: Initial sorting is O(N^2) (could be O(N log N), but who cares ). Every point is compared at most once with every other point. (when comparing ycoordinates) That gives us O(N^2).
To the complexity analysis: Initial sorting is O(N^2) (could be O(N log N), but who cares ). Every point is compared at most once with every other point. (when comparing ycoordinates) That gives us O(N^2).
Using Map
We never solved it during the online contest, but we used <map>. It was indexed on X, and the value at X was Y. So, we would go through each of the X's, and then try to follow a rectangle. If we couldn't do that, then there wasn't a rectangle. Didn't get it to work though.
During the contest I've tougth of implementing marian's solution but I wasn't sure the solution wasn't too slow. I implemented first the n^2 log n solution wich got tle and then I tried marking the points on a matrix and do the n^2 solution. Because there are only 5000 points there are only 5000 different x coordinates and 5000 different y coordinates so we can normalize the coordinates so all the points have integer coordinates in [0,5000]X[0,5000]. So for the simple n^2 solution you need a 25Mb matrix and I thougth that uva allowed less so I switched my implementation to a bit matrix and I still got TLE ,for geting the bit in the matrix wich represented x,y I used some bit operations and I tried optimising this using precumputations and this got me accepted in 2.97 (the time limit in the contest was 3 s). After the contest I've heard that C++ and Pascal source code using 25 Mb got tle, maybe this is because working with more memory is slower.
Could you tell me how to normalize the coordinates so all the points have integer coordinates?Cosmin.ro wrote: Because there are only 5000 points there are only 5000 different x coordinates and 5000 different y coordinates so we can normalize the coordinates so all the points have integer coordinates in [0,5000]X[0,5000].
regards,
tep
http://www.harvestsoft.net
Stephanus
Stephanus
I'm still confused... Then how do I search in O(1) if there is point (x,y)?
Are you using n^2 algorithm ?
Are you using n^2 algorithm ?
http://www.harvestsoft.net
Stephanus
Stephanus
Umm.. sorry I still don't understand..
for example we have 3 point (x,y)
1e9 , 2e9
1e8 , 2e8
1e7 , 2e7
so, x[1] = 1e9, x[2] = 1e8, x[3] = 1e7
y[1] = 2e9, y[2] = 2e8, y[3] = 2e7
now if i want to search whether (1e8,2e6) exists?
then i search in x array 1e8? found in index 2
search in y array 2e6? not found, so the point doesn't exist.
if we can found both, then we check the big table?
Is it the way?
thanks..
for example we have 3 point (x,y)
1e9 , 2e9
1e8 , 2e8
1e7 , 2e7
so, x[1] = 1e9, x[2] = 1e8, x[3] = 1e7
y[1] = 2e9, y[2] = 2e8, y[3] = 2e7
now if i want to search whether (1e8,2e6) exists?
then i search in x array 1e8? found in index 2
search in y array 2e6? not found, so the point doesn't exist.
if we can found both, then we check the big table?
Is it the way?
thanks..
http://www.harvestsoft.net
Stephanus
Stephanus

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
No, basically, for me anyhow, you store x, y, rx, ry, where rx, ry are the renormalized x, y. After sorting your 3 points, you get:
1e9 , 2e9, 2, 2
1e8 , 2e8, 1, 1
1e7 , 2e7, 0, 0
(I actually don't store the rx, ry explicitly)
As mentioned above, you have a big 5000x5000 array, and you don't need the original numbers anymore.. a rectangle exist when there exists four corners, so for a O(n^2) algorithm, you basically have:
for each point a
for each point b
if a_x, b_y exists and if a_y, b_x exists
increment counter
And you can check if a renormalized point exists in O(1), by checking array.
My program doesn't run under 3 seconds though, so I'l be curious as to how to solve it in so much faster..
1e9 , 2e9, 2, 2
1e8 , 2e8, 1, 1
1e7 , 2e7, 0, 0
(I actually don't store the rx, ry explicitly)
As mentioned above, you have a big 5000x5000 array, and you don't need the original numbers anymore.. a rectangle exist when there exists four corners, so for a O(n^2) algorithm, you basically have:
for each point a
for each point b
if a_x, b_y exists and if a_y, b_x exists
increment counter
And you can check if a renormalized point exists in O(1), by checking array.
My program doesn't run under 3 seconds though, so I'l be curious as to how to solve it in so much faster..
Please help.. I don't know why I still got TLE..
I've used the method (normalizing) above..
thanx
[cpp]// Problem : Counting Rectangles
// UVA id : 10574
// Lang. : C++
// Author : Stephanus Indra
// Date : 29 December 2003
#include <iostream>
#include <cstdlib>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define MAX_N 5000
using namespace std;
class Point {
public:
int x,y;
int rx,ry;
};
Point point[MAX_N];
int p[MAX_N][157]; // 157 = 1 + N/BITSPERWORD
int npoint;
void set(int x,int y) { p[y][x >> SHIFT] = (1 << (x & MASK)); }
void clr(int x,int y) { p[y][x >> SHIFT] &= ~(1 << (x & MASK)); }
int test(int x,int y) { return p[y][x >> SHIFT] & (1 << (x & MASK)); }
int pxcmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;
if (a>x == b>x)
return a>y  b>y;
else
return a>x  b>x;
}
int pycmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;
if (a>y == b>y)
return a>x  b>x;
else
return a>y  b>y;
}
int main()
{
int ncase,n;
int i,j,nrect;
cin >> ncase;
for (n=1; n<=ncase; n++)
{
// get input
cin >> npoint;
for (i=0; i<npoint; i++)
for (j=0; j<npoint; j++)
clr(i,j);
for (i=0; i<npoint; i++)
cin >> point.x >> point.y;
// sort,normalize  x
qsort(point,npoint,sizeof(Point),pxcmp);
point[0].rx = 0;
for (i=1; i<npoint; i++)
if (point.x != point[i1].x)
point.rx = point[i1].rx + 1;
else
point.rx = point[i1].rx;
// sort,normalize  y
qsort(point,npoint,sizeof(Point),pycmp);
point[0].ry = 0;
for (i=1; i<npoint; i++)
if (point.y != point[i1].y)
point.ry = point[i1].ry + 1;
else
point.ry = point[i1].ry;
// sign xy
for (i=0; i<npoint; i++)
set(point.rx,point.ry);
// solve
nrect = 0;
for (i=0; i<npoint; i++)
for (j=i+1; j<npoint; j++)
if (point[i].ry < point[j].ry && point[i].rx < point[j].rx && test(point[i].rx,point[j].ry) && test(point[j].rx,point[i].ry))
nrect++;
// output
cout << "Case " << n << ": " << nrect << endl;
}
return 0;
}[/cpp]
I've used the method (normalizing) above..
thanx
[cpp]// Problem : Counting Rectangles
// UVA id : 10574
// Lang. : C++
// Author : Stephanus Indra
// Date : 29 December 2003
#include <iostream>
#include <cstdlib>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define MAX_N 5000
using namespace std;
class Point {
public:
int x,y;
int rx,ry;
};
Point point[MAX_N];
int p[MAX_N][157]; // 157 = 1 + N/BITSPERWORD
int npoint;
void set(int x,int y) { p[y][x >> SHIFT] = (1 << (x & MASK)); }
void clr(int x,int y) { p[y][x >> SHIFT] &= ~(1 << (x & MASK)); }
int test(int x,int y) { return p[y][x >> SHIFT] & (1 << (x & MASK)); }
int pxcmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;
if (a>x == b>x)
return a>y  b>y;
else
return a>x  b>x;
}
int pycmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;
if (a>y == b>y)
return a>x  b>x;
else
return a>y  b>y;
}
int main()
{
int ncase,n;
int i,j,nrect;
cin >> ncase;
for (n=1; n<=ncase; n++)
{
// get input
cin >> npoint;
for (i=0; i<npoint; i++)
for (j=0; j<npoint; j++)
clr(i,j);
for (i=0; i<npoint; i++)
cin >> point.x >> point.y;
// sort,normalize  x
qsort(point,npoint,sizeof(Point),pxcmp);
point[0].rx = 0;
for (i=1; i<npoint; i++)
if (point.x != point[i1].x)
point.rx = point[i1].rx + 1;
else
point.rx = point[i1].rx;
// sort,normalize  y
qsort(point,npoint,sizeof(Point),pycmp);
point[0].ry = 0;
for (i=1; i<npoint; i++)
if (point.y != point[i1].y)
point.ry = point[i1].ry + 1;
else
point.ry = point[i1].ry;
// sign xy
for (i=0; i<npoint; i++)
set(point.rx,point.ry);
// solve
nrect = 0;
for (i=0; i<npoint; i++)
for (j=i+1; j<npoint; j++)
if (point[i].ry < point[j].ry && point[i].rx < point[j].rx && test(point[i].rx,point[j].ry) && test(point[j].rx,point[i].ry))
nrect++;
// output
cout << "Case " << n << ": " << nrect << endl;
}
return 0;
}[/cpp]
http://www.harvestsoft.net
Stephanus
Stephanus