10173  Smallest Bounding Rectangle
Moderator: Board moderators
10173
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
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

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

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
mm.. I rotate it from PI~PI using rotation matrix, inc theta by PI/1800Ivan Golubev wrote: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 wrote:is there always one side of input polygon be the same side of the smallest rectangle ?
but WA...
if only contain two points... the answer should be 0.0000 ?
can you give me more test case... thank you

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

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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 1e12.Even wrote:mm.. I rotate it from PI~PI using rotation matrix, inc theta by PI/1800
Yes, answer must be 0.0000.Even wrote:if only contain two points... the answer should be 0.0000 ?
Some tests, input:
Output: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
80.0000
100.0000
50.0000
107029.2217
0.0000
0.0000
0.0000
thank you~~~
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 ?? ...
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 ?? ...
Re: thank you~~~
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
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 ?? ...
Re: thank you~~~
hmm...only one constrain ... fit tightly ...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
and I think it can be solve by the same method... thank you
Getting WA
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[nh1], p[at], p);
if (z > 0) {
at = i;
} else if (fabs(z) < 0.00000001) {
double d1, d2;
d1 = QUAD(h[nh1].x  p[at].x) + QUAD(h[nh1].y  p[at].y);
d2 = QUAD(h[nh1].x  p.x) + QUAD(h[nh1].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 = tinc;
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.
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[nh1], p[at], p);
if (z > 0) {
at = i;
} else if (fabs(z) < 0.00000001) {
double d1, d2;
d1 = QUAD(h[nh1].x  p[at].x) + QUAD(h[nh1].y  p[at].y);
d2 = QUAD(h[nh1].x  p.x) + QUAD(h[nh1].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 = tinc;
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.
Sorry for confusing you,jpfarias wrote:How do you find the interval to search next?
JP.
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