10577 - Bounding box

[Almorrana]

My algorithm is as follows:

1. If numVertex=3
Calc the bounding box just getting the max/min x/y coords

2. If numVertex > 3
Calc the circumcenter of the three vertex, and then, with one given vertex and the circumcenter, generate all the numVertex vertices (circunference equation). With all these points, calc the max/min on x/y coords to get the bounding box.

Something wrong? With all the test cases it works fine.
Thx

[Larry]

Sounds right. Perhaps you have a precision problem?

[Adrian Kuegel]

I used the same algorithm, and I had a precision problem, too. Because I didn't know what was wrong I checked my program with the Waterloo Test Cases. Only for one input I got a different output, so I made a special case for it.

[ginie]

Hi people!!
Does anybody know what's the problem with my code for 10577?
I calculate the incenter of the traingle made with the 4 vertex and then calcule the other ones knowing that the polygon is regular and with n sides.
#include <iostream.h>
#include <stdio.h>
#include <math.h>

const float pi=3.14159265358979323846f;

double max(double x, double y)
{
double maxi;
if (x>y) maxi=x;
else maxi=y;
return(maxi);
}
double min(double x, double y)
{
double mini;
if (x<y) mini=x;
else mini=y;
return(mini);
}
void main()
{
int n,num,i;
double x[150],y[150],area,r0,r1,r2,xc,yc,x0,x1,x2,y0,y1,y2,cs,sn,maximx,minimx,maximy,minimy;

num=num^num;
cin >> n;
while(n!=0)
{
num++;
cin >> x[0]>> y[0];
cin >> x[1]>> y[1];
cin >> x[2]>> y[2];

if(n==3)
{
maximx=x[0];minimx=x[0];maximy=y[0];minimy=y[0];
for(i=1; i<3; i++)
{
maximx=max(maximx,x);
maximy=max(maximy,y);
minimx=min(minimx,x);
minimy=min(minimy,y);
}

area=(maximx-minimx)*(maximy-minimy);
}
else
{
r0=x[0]*x[0]+y[0]*y[0];
r1=x[1]*x[1]+y[1]*y[1];
r2=x[2]*x[2]+y[2]*y[2];
x0=y[1]-y[2];y0=x[1]-x[2];
x1=y[2]-y[0];y1=x[2]-x[0];
x2=y[0]-y[1];y2=x[0]-x[1];
xc=(r0*x0+r1*x1+r2*x2)/(2*(x[0]*x0+x[1]*x1+x[2]*x2));
yc=(r0*y0+r1*y1+r2*y2)/(2*(y[0]*y0+y[1]*y1+y[2]*y2));
for(i=1; i<n; i++)
{
cs=cos(2*pi*i/n);sn=sin(2*pi*i/n);
x=x[0]*cs-y[0]*sn+xc;
y=x[0]*sn+cs*y[0]+yc;
}

maximx=x[0];minimx=x[0];maximy=y[0];minimy=y[0];
for(i=1; i<n; i++)
{
maximx=max(maximx,x);
maximy=max(maximy,y);
minimx=min(minimx,x);
minimy=min(minimy,x);
}

area=(maximx-minimx)*(maximy-minimy);

}

cout <<"Polygon "<< num <<": "<< area<<endl;
cin >> n;
}
}

[minskcity]

Where can I find those "Waterloo Test Cases"?

[WR]

http://plg.uwaterloo.ca/~acm00/

[minskcity]

Thanks. I looked over the page, but could not find the "bounding box" problem . Do you have any idea where it can be? I looked at contests dated 2001+, because on UVA it says "Local_UVa'2003"...

[daveon]

Hi,

Look for 22 September 2001 - Waterloo local contest
PROBLEM D.

[minskcity]

Thanks, got AC now

[HHH]

can you plz post these cases as the page don't want to open with me

[HHH]

Hi,

Look for 22 September 2001 - Waterloo local contest
PROBLEM D.

plz I need these cases

[blegat]

Important details, output the numbers with exactly 3 decimals or you will get WA.
Here are the inpust/outputs