10173 - Smallest Bounding Rectangle

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

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

10173

Post by cyfra » Thu Jun 13, 2002 3:07 pm

Hi!

I have a small problem with this task...

It loks quite easy but my program always gets WA :cry:

I take the smallest and largest values of x and y and count the area of the rectangle...

Are there any tricky inputs or something like that...

Pls Help

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jun 13, 2002 3:50 pm

Input:
4
0 5
-5 0
5 0
0 -5
0

Output:
50.0000

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Thu Oct 24, 2002 9:17 am

hello Ivan...

is there always one side of input polygon be the same side of the smallest rectangle ?

I always consider one side of convex ( form by input )
be one side of the smallest rectangle ...but WA... ><

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Oct 24, 2002 2:03 pm

Even wrote:is there always one side of input polygon be the same side of the smallest rectangle ?
I'm not sure about this. My accepted solution computes convex hull and then rotates it from 0 to pi/2 to find smallest possible rectangle.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Thu Oct 24, 2002 5:39 pm

Ivan Golubev wrote:
Even wrote:is there always one side of input polygon be the same side of the smallest rectangle ?
I'm not sure about this. My accepted solution computes convex hull and then rotates it from 0 to pi/2 to find smallest possible rectangle.
mm.. I rotate it from -PI~PI using rotation matrix, inc theta by PI/1800

but WA... :cry:

if only contain two points... the answer should be 0.0000 ?

can you give me more test case... thank you :)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Oct 24, 2002 7:21 pm

Do you rotate using the original polygon? If not, you will have precision errors. And there is always one side of the convex hull that has a common side with the smallest rectangle.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Oct 24, 2002 7:41 pm

Even wrote:mm.. I rotate it from -PI~PI using rotation matrix, inc theta by PI/1800
May be pi/1800 is not enough precise -- my solution starts from theta == 0.1 and searching for smallest rectangle. Then decreasing theta 10 times and seaching in smaller (founded) interval. This process appling several times and last theta value is about 1e-12.
Even wrote:if only contain two points... the answer should be 0.0000 ?
Yes, answer must be 0.0000.
Some tests, input:
3
-3.000000 5.000000
17.000000 5.000000
7.000000 9.000000
4
10.000000 10.000000
20.000000 10.000000
20.000000 20.000000
10.000000 20.000000
4
-5.000000 0.000000
0.000000 -5.000000
5.000000 0.000000
0.000000 5.000000
21
211.330000 0.360000
277.690000 0.300000
288.740000 0.440000
327.450000 1.240000
327.630000 122.950000
327.660000 232.820000
319.980000 314.840000
303.210000 326.900000
138.970000 327.310000
91.490000 327.240000
73.410000 327.060000
8.600000 323.920000
7.630000 323.670000
1.520000 289.180000
0.310000 232.200000
0.100000 22.700000
5.770000 6.350000
7.120000 3.800000
80.300000 1.770000
134.550000 0.920000
199.580000 0.410000
1
1.0 1.0
2
3.0 3.0
0 0
3
0 0
1 1
2 2
0
Output:
80.0000
100.0000
50.0000
107029.2217
0.0000
0.0000
0.0000

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

thank you~~~

Post by Even » Mon Oct 28, 2002 7:41 am

thank Ivan Golubev and Adrian Kuegel...

I starts form theta = 0, inc = 1 to searching for the smallest rectangle.
Then decreasing inc to inc/10, searching in smaller interval...
repeat ...10 times ... WA ... 11 times ... AC :)

thank you all ....

and If I wanna search the "largest" rectangle...
can I use the same method ?? ...

Google
New poster
Posts: 4
Joined: Wed Sep 18, 2002 5:32 pm

Re: thank you~~~

Post by Google » Thu Oct 31, 2002 4:57 am

The largest rectangle is simply infinitely large.
I think your proposition need some more definitions.
Maybe you want to put the constraints on the rectangle that should
have at least a certain number of points on the boundary or something else...I don't know

Even wrote:thank Ivan Golubev and Adrian Kuegel...

I starts form theta = 0, inc = 1 to searching for the smallest rectangle.
Then decreasing inc to inc/10, searching in smaller interval...
repeat ...10 times ... WA ... 11 times ... AC :)

thank you all ....

and If I wanna search the "largest" rectangle...
can I use the same method ?? ...

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Re: thank you~~~

Post by Even » Thu Oct 31, 2002 8:45 am

Google wrote:The largest rectangle is simply infinitely large.
I think your proposition need some more definitions.
Maybe you want to put the constraints on the rectangle that should
have at least a certain number of points on the boundary or something else...I don't know
hmm...only one constrain ... fit tightly ...

and I think it can be solve by the same method... thank you :)

hager
New poster
Posts: 10
Joined: Wed Jan 01, 2003 4:26 am
Location: Ume

Post by hager » Tue Jun 17, 2003 12:20 pm

I have not solved this problem, but I seem to remember that the bounding rectangle is not necessarily oriented with two vertical and two horizontal lines, i.e. it must be rotated to minimize the area when enclosing certain sets of points. Hope this helps.

Best regards

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Getting WA

Post by jpfarias » Fri Nov 28, 2003 5:05 pm

Hi!

Can you find why I'm getting WA?

Here is my code:

[cpp]
#include <stdio.h>
#include <math.h>

typedef struct Ponto {
double x;
double y;
} Ponto;

Ponto p[1010];
int n;

Ponto h[1010];
int nh;
int idx[1010];

double minY, maxY, minX, maxX;
double minA;

double prod_vet_z(Ponto &a, Ponto &b, Ponto &c) {
Ponto p1, p2;
p1.x = b.x - a.x;
p1.y = b.y - a.y;
p2.x = c.x - a.x;
p2.y = c.y - a.y;
return (p1.x * p2.y - p1.y * p2.x);
}
#define QUAD(x) ((x) * (x))
void jarvin_march() {
Ponto menor = { 1.0e+99, 1.0e+99 };
int menor_i;
for ( int i = 0; i < n; ++i ) {
if (p.y < menor.y || (p.y == menor.y && p.x < menor.x)) {
menor.x = p.x;
menor.y = p.y;
menor_i = i;
}
}

nh = 1;
h[0].x = menor.x;
h[0].y = menor.y;
idx[0] = menor_i;
int at;

do {
at = 0;
for (int i=1; i<n; ++i) {
double z = prod_vet_z(h[nh-1], p[at], p);
if (z > 0) {

at = i;
} else if (fabs(z) < 0.00000001) {
double d1, d2;
d1 = QUAD(h[nh-1].x - p[at].x) + QUAD(h[nh-1].y - p[at].y);
d2 = QUAD(h[nh-1].x - p.x) + QUAD(h[nh-1].y - p.y);
if (d1 < d2) {
at = i;
}
}
}
h[nh].x = p[at].x;
h[nh].y = p[at].y;
idx[nh] = at;
++nh;
} while (at != menor_i);

}

void rotate(double a) {
double c = cos(a);
double s = sin(a);

for (int i=0; i<nh; ++i) {
double rx, ry;
rx = c * p[idx].x + s * p[idx].y;
ry = -s * p[idx[i]].x + c * p[idx[i]].y;
h[i].x = rx;
h[i].y = ry;
}

}

void rotate1(double a) {
double c = cos(a);
double s = sin(a);

for (int i=0; i<n; ++i) {
double rx, ry;
rx = c * p[i].x + s * p[i].y;
ry = -s * p[i].x + c * p[i].y;
h[i].x = rx;
h[i].y = ry;
}

}


double findMinArea() {
minX = minY = 1.0e+99;
maxX = maxY = -1.0e+99;
for (int i=0; i<nh; ++i) {
if (h[i].x < minX) {
minX = h[i].x;
}
if (h[i].y < minY) {
minY = h[i].y;
}
if (h[i].x > maxX) {
maxX = h[i].x;
}
if (h[i].y > maxY) {
maxY = h[i].y;
}
}
double a = (maxX - minX) * (maxY - minY);
return a;
}

double findMinArea1() {
minX = minY = 1.0e+99;
maxX = maxY = -1.0e+99;
for (int i=0; i<n; ++i) {
if (h[i].x < minX) {
minX = h[i].x;
}
if (h[i].y < minY) {
minY = h[i].y;
}
if (h[i].x > maxX) {
maxX = h[i].x;
}
if (h[i].y > maxY) {
maxY = h[i].y;
}
}
double a = (maxX - minX) * (maxY - minY);
return a;
}


int main() {
double PI = 2*acos(0);

for (;;) {
scanf("%d", &n);
if (!n) {
break;
}

for (int i=0; i<n; ++i) {
scanf("%lf %lf", &p[i].x, &p[i].y);
}
p[n].x = p[0].x;
p[n].y = p[0].y;
++n;
if (n>3) {
jarvin_march();
} else {
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
nh = n;
}
minA = 1.0e+99;
double inc = 1;
double left = 0, right = PI/2.0;
double newleft = left;
double newright = right;
bool foundMin = false;
for ( int k=0; k<15; ++k) {
minA = 1.0e+99;
for ( double t = left; t <= right; t += inc ) {
rotate1(t);
double at = findMinArea1();
if (at < minA) {
minA = at;
foundMin = true;
newleft = t-inc;
newright = t+inc;
}
}
left = newleft;
right = newright;
inc /= 10.0;
}
printf("%.4lf\n", minA);

}
return 0;
}
[/cpp]

On the above, rotate and findMinArea uses the convex hull, and rotate1 and findMinArea1 don't. Both gives me WA :-(

JP.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Fri Nov 28, 2003 6:26 pm

How do you find the interval to search next?

JP.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Sat Nov 29, 2003 2:19 am

jpfarias wrote:How do you find the interval to search next?

JP.
Sorry for confusing you,
I wrote that "inc = 1" means 1 degree ( PI/180 ), not 1.

for the interval, I choice a middle point, and add/sub a range to form the new one.
In the begining, mid = PI/4.0, range = PI/4.0, interval will be ( 0, PI/2.0 )
for each iteration, find the minimal area and the rotational angle would be the next middle point.
for each iteration, set range equal to the increment, and reduce increment to 10 times.

Mr. Even

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sat Nov 29, 2003 3:28 am

Thanks! Got Accepted now! :-D

JP.

Post Reply

Return to “Volume 101 (10100-10199)”