10173 - Smallest Bounding Rectangle

[cyfra]

Hi!

I have a small problem with this task...

It loks quite easy but my program always gets WA

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]

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

Output:
50.0000

[Even]

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]

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]

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...

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

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

[Adrian Kuegel]

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]

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.

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]

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]

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

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]

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]

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]

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]

How do you find the interval to search next?

JP.

[Even]

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]

Thanks! Got Accepted now!

JP.