Page 2 of 4
Posted: Thu Jun 20, 2002 2:30 pm
by Revenger
You wrote
1. Given two points the unique minimal radius circle intersecting these is the circle with center in the middle and half the distance as radius.
Can you explain it to me on example
Posted: Thu Jun 20, 2002 3:59 pm
by arnsfelt
I believe your programs does not do what I said...
Posted: Fri Sep 20, 2002 2:58 pm
by oracle
arnsfelt wrote:
- 1. Given two points the unique minimal radius circle intersecting these is the circle with center in the middle and half the distance as radius.
2. Given three points that are not colinear there is a unique circle that intersect these.
3. Given n>1 points it it possible to choose two or three points such that the minimal circle including all the points is as descriped above.
Do you think the above algorithm is correct. Have anyone using that algorithm got ACCEPTED SUBMITION ?.
10005 - Packing polygons ...
Posted: Mon Dec 09, 2002 1:28 pm
by Dominik Michniewski
Could anyone help me and posts counterexample, in which my algorithm fails ?
Code: Select all
EPS ==> 1e-9
N - number of points in polygon
R *= 2.0; /* diameter of circle */
max = 0.0;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
{
x = points[i][0] - points[j][0];
y = points[i][1] - points[j][1];
tmp = x*x + y*y;
if(tmp > max) max = tmp;
}
max = sqrt(max) + EPS;
if(max <= R)
printf("The polygon can be packed in the circle.\n");
else
printf("There is no way of packing that polygon.\n");
Posted: Mon Dec 09, 2002 1:38 pm
by Adrian Kuegel
3
0 0
0 4
3 2
2.0
0
I think you will print that it is possible to pack that polygon, but it is not.
Posted: Mon Dec 09, 2002 2:59 pm
by Dominik Michniewski
Thanks Adrian for this input ....
I have to think deeper about this problem ....
Dominik
10005-Wrong Answer-Help me
Posted: Mon Jan 13, 2003 6:19 am
by Eddy
This is my code:
{ @JUDGE_ID: 27272HH 10005 Pascal "Packing polygons" }
Program p10005 (input,output);
var x,y:array[1..200] of integer;
n,i,maxX,maxY,minX,minY:integer;
r:real;
Procedure Solve;
var centerX,centerY,distance:real;
result:boolean;
i:integer;
Begin
{A1(minX,maxY),A2(maxX,maxY),A3(maxX,minY),A4(minX,minY)}
result:=true;
centerX:=(maxX+minX)/2;
centerY:=(maxY+minY)/2;
for i:=1 to n do
Begin
distance:=sqrt(sqr(x-centerx)+sqr(y-centerY));
if distance>r then
Begin
result:=false;break;
End;
End;
if result=true then
writeln('The polygon can be packeg in the circle.')
else writeln('There is no way the packing of polygon.');
End;
BEGIN
readln(n);
while n<>0 do
Begin
maxX:=-32768;maxY:=-32768;
minX:=32767;minY:=32767;
for i:=1 to n do
Begin
readln(x,y);
if x>maxX then maxX:=x;
if x<minX then minX:=x;
if y>maxY then maxY:=y;
if y[i]<minY then minY:=y[i];
End;
readln(r);
solve;
readln(n);
End;
END.
The Judge system reported "Wrong Answer".
Help Me.
Thanks![pascal][/pascal]
10005-Wrong Answer-Help me
Posted: Wed Jan 22, 2003 2:31 pm
by Eddy
This is my code:
{ @JUDGE_ID: 27272HH 10005 Pascal "Packing polygons" }
Program p10005 (input,output);
var x,y:array[1..200] of integer;
n,i,maxX,maxY,minX,minY:integer;
r:real;
Procedure Solve;
var centerX,centerY,distance:real;
result:boolean;
i:integer;
Begin
{A1(minX,maxY),A2(maxX,maxY),A3(maxX,minY),A4(minX,minY)}
result:=true;
centerX:=(maxX+minX)/2;
centerY:=(maxY+minY)/2;
for i:=1 to n do
Begin
distance:=sqrt(sqr(x-centerx)+sqr(y-centerY));
if distance>r then
Begin
result:=false;break;
End;
End;
if result=true then
writeln('The polygon can be packeg in the circle.')
else writeln('There is no way the packing of polygon.');
End;
BEGIN
readln(n);
while n<>0 do
Begin
maxX:=-32768;maxY:=-32768;
minX:=32767;minY:=32767;
for i:=1 to n do
Begin
readln(x,y);
if x>maxX then maxX:=x;
if x<minX then minX:=x;
if y>maxY then maxY:=y;
if y[i]<minY then minY:=y[i];
End;
readln(r);
solve;
readln(n);
End;
END.
The Judge system reported "Wrong Answer".
Help Me.
Thanks![pascal][/pascal]
10005
Posted: Wed May 28, 2003 10:19 pm
by superraskao
I get WA with this code, can anyone help?
[c]
#include <stdio.h>
#include <math.h>
float X[100];
float Y[100];
int N;
float M[2][3];
float tc[2];
void resolver()
{
float c;
float * F1;
float * F2;
F1 = M[0];
F2 = M[1];
if(M[0][0] == 0)
{
F1 = M[1];
F2 = M[0];
}
else
{
c = M[1][0]/M[0][0];
M[1][1] = M[1][1] - M[0][1]*c;
M[1][2] = M[1][2] - M[0][2]*c;
}
tc[1] = F2[2] / F2[1];
tc[0] = (F1[2] - (tc[1]*F1[1]))/F1[0];
}
float cruz(int a, int b, int c)
{
return((X[a]-X[c]) * (Y - Y[c]) - (X-X[c]) * (Y[a] - Y[c]));
}
float distancia(int i, float x, float y)
{
float xd,yd;
xd = (x - X);
yd = y - Y;
return(xd*xd + yd*yd);
}
int contiene(float x, float y, float r)
{
int i;
double r2;
r2 = r*r;
for(i = 0; i < N; i++)
{
if(distancia(i,x,y) > r)
{
return 0;
}
}
return 1;
}
int puede(float r)
{
int i, j, k;
float rt, xt, yt;
for(i = 0; i < N; i++)
{
for(j = i+1; j < N; j++)
{
xt =(X + X[j])/2;
yt =(Y + Y[j])/2;
rt = distancia(i,X[j],Y[j])/4;
if(contiene(xt,yt,rt))
{
if(r >= rt)
{
return(1);
}
}
for(k = j+1; k < N; k++)
{
if(cruz(i,j,k) != 0)
{
M[0][0] = 2*(X[k] - X);
M[0][1] = 2*(Y[k] - Y);
M[0][2] = Y[k]*Y[k] + X[k]*X[k] - X*X - Y*Y;
M[1][0] = 2*(X[j] - X[i]);
M[1][1] = 2*(Y[j] - Y[i]);
M[1][2] = Y[j]*Y[j] + X[j]*X[j] - X[i]*X[i] - Y[i]*Y[i];
resolver();
rt = distancia(i,tc[0],tc[1]);
xt = tc[0];
yt = tc[1];
if(contiene(xt,yt,rt))
{
if(r >= rt)
{
return(1);
}
}
}
}
}
}
return(0);
}
main()
{
float r;
int p,i;
freopen("p10005.in", "r", stdin);
scanf("%d",&N);
while(N > 0)
{
for(i = 0; i < N; i++)
{
scanf("%f %f",&X[i],&Y[i]);
}
scanf("%f",&r);
p = 0;
if(N > 1)
{
p = puede(r);
}
else
p = 1;
if(p)
printf("The polygon can be packed in the circle.\n");
else
printf("There is no way of packing that polygon.\n");
scanf("%d",&N);
}
}
[/c]
10005 (Packing Polygons) VERY fast solutions
Posted: Wed Feb 04, 2004 7:30 pm
by alex[LSD]
The thing is - My solution is N^3. I am #326 of 331 in the promlems list with 1.68s.
So please, enlighten my butt, tell me about how to solve it fast.
P.S. I d really appreciate that.
Re: 10005 (Packing Polygons) VERY fast solutions
Posted: Sun Feb 08, 2004 2:23 am
by horape
alex[LSD] wrote:The thing is - My solution is N^3. I am #326 of 331 in the promlems list with 1.68s.
So please, enlighten my butt, tell me about how to solve it fast.
P.S. I d really appreciate that.
My solution is O(N^3) too, and runs on 0.004 seconds.
For each pair of points i calc the circle of radius R that has that pair of points on the perimeter, and then test inclusion of all the
points on that circle.
Saludos,
HoraPe
Posted: Sun Feb 08, 2004 8:01 am
by alex[LSD]
Horape I dont get what do you mean by "test".
I also went through all the pairs, and for each pair I found the MINIMUM ANGLE from a 3rd point to the line segment. I needed minimum angles for two cases separately : for "above" the line segment and for "below". Did you do smth like this? I guess my GetAngle() was too time-consuming...
Posted: Sun Feb 08, 2004 3:06 pm
by horape
alex[LSD] wrote:Horape I dont get what do you mean by "test".
I also went through all the pairs, and for each pair I found the MINIMUM ANGLE from a 3rd point to the line segment. I needed minimum angles for two cases separately : for "above" the line segment and for "below". Did you do smth like this? I guess my GetAngle() was too time-consuming...
Hmmm, for each pair of points I get the center of the circle of radius R that has them on the perimeter. Simple geometry:
Code: Select all
ab = b-a; // vector
abp = perp(ab); // perp (x,y) = (y,-x)
d = dist(a,b)
if (d>2*R)
there is no way for a circle of radius R to include both points.
// dp
Posted: Mon Feb 09, 2004 7:22 am
by alex[LSD]
Sounds like binary search.
So where do you get the R value? And why dont you go both directions from middle of AB?
Posted: Mon Feb 09, 2004 8:16 am
by horape
alex[LSD] wrote:Sounds like binary search.
So where do you get the R value? And why dont you go both directions from middle of AB?
It isn't binary search, nor something like that, as far as i understand. I test each pair of vertices, and then test it again every vertex.
The last line of the input case will be a real number indicating the radius R of the circle.
And I do AB and BA, that's why I just choose one of the points and not both.
Saludos,
HoraPe