10697 - Firemen barracks

[sergio]

> I think programming problems should concentrate on solving programming
> questions, not on how a particular compiler in a particular environment prints
> numbers.

I think solving programming questions is most important too. But during the contest we receive some complains about the -0.0 and in fact -0.0 does not exist

[liulike]

I got AC now!

Thanks every one!

[Observer]

Well, I still get WA....... Why.....

My program passes the test cases above perfectly, yet.......

Can anyone please help? Or should I rewrite the whole thing in C/C++?

[Edit] I've implemented a C code, which gets WA as well!!! Could anyone please give me some critical test cases?
My solution is similar to that of 190 Circles through 3 pts... Needless to say, I get AC for that problem.

[sergio]

I friend mine also got AC in the problem 190 but he was getting WA in this problem. When we tested his program it failed in this input:

0.7 1.0 0.9 0.2 0.1 0.2

The answer should be:
The equidistant location is (0.5, 0.5).

He was getting something like (nan, nan)
But I think it is a little bit difficult that you have the same error
I can also post more test cases if you want[/java]

[_.B._]

Took me more than 20 submissiones to get it ACed.
I'm using FreePascal.
Read posts below for I/O.

[Per]

> I think programming problems should concentrate on solving programming
> questions, not on how a particular compiler in a particular environment prints
> numbers.

I think solving programming questions is most important too. But during the contest we receive some complains about the -0.0 and in fact -0.0 does not exist

Yes, and that was because there was no special judge, which made it very hard to guess for which cases the output was supposed to be "-0.0" and for which it was supposed to be "0.0"
Now that there is a special judge, I agree with joey that "-0.0" should be allowed.

I find it a bit strange that this problem needs a special judge at all, given that the output only needs to be accurate in the first decimal.

[Meng-Hsuan Wu]

Hello!

My program passes all the test cases mentioned above but it gets Wrong Answer. Is it because my accuracy is inadequate? Or is there anything wrong when I round the numbers to 1 decimal place? (P.S. When I decide whether two slopes are the same, I allow an error of 1e-14.)

By the way, if a coordinate is -1.75, should I print it as -1.7 or -1.8?

Please help me with these problems. Thank you very much!

Meng-Hsuan Wu

[cpp]
#include <stdio.h>
main(){
int n,i;
double x1,y1,x2,y2,x3,y3,cx1,cy1,m1,b1,cx2,cy2,m2,b2,r1,rx,ry;
scanf("%d\n",&n);
for(i=1;i<=n;i++){
scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
if((x1==x2&&y1==y2)||(x1==x3&&y1==y3)||(x2==x3&&y2==y3))
printf("There is an infinity of possible locations.\n");
else{
cx1=(x1+x2)/2.0;
cy1=(y1+y2)/2.0;
if(y1==y2){
m1=1e30;
b1=cx1;
}
else{
m1=-(x2-x1)/(y2-y1);
b1=cy1-m1*cx1;
}
cx2=(x1+x3)/2.0;
cy2=(y1+y3)/2.0;
if(y1==y3){
m2=1e30;
b2=cx2;
}
else{
m2=-(x3-x1)/(y3-y1);
b2=cy2-m2*cx2;
}
if(m1==m2||(m1!=0.0&&m2!=0.0&&m1/m2>=1-1e-14&&m1/m2<=1+1e-14))
printf("There is no possible location.\n");
else{
if(m1==1e30){
rx=b1;
ry=m2*rx+b2;
}
else if(m2==1e30){
rx=b2;
ry=m1*rx+b1;
}
else{
rx=(b1-b2)/(m2-m1);
ry=(b1*m2-b2*m1)/(m2-m1);
}
if(rx<0.0&&rx>-0.05)
rx=0.0;
if(ry<0.0&&ry>-0.05)
ry=0.0;
printf("The equidistant location is (%.1lf, %.1lf).\n",rx,ry);
}
}
}
}
[/cpp]

[Observer]

When we tested his program it failed in this input:
0.7 1.0 0.9 0.2 0.1 0.2
The answer should be:
The equidistant location is (0.5, 0.5).

Yes I get this right.

I can also post more test cases if you want.

Please do so~

[dll]

I pass all test cases, but still got WA.
I am unable to find the bug of my program now

[sergio]

When I decide whether two slopes are the same, I allow an error of 1e-14.

It is OK.
I am putting some more test cases:
INPUT
10
0.3 0.5 0.0 0.9 0.2 0.8
0.4 1.0 1.4 0.6 0.4 1.0
1.7 0.7 12.5 3.2 0.1 15.7
3.3 4.6 2.3 0.5 2.2 3.1
333.6 1.4 0.8 0.6 2.0 0.9
1.3 1.9 0.1 1.4 0.0 0.7
0.0 0.7 1.6 1.0 0.1 0.1
0.2 0.6 1.9 5.7 2.1 6.3
0.8 1.1 0.3 0.3 1.6 1.1
0.8 1.1 0.2 5.0 0.6 0.7

OUTPUT
The equidistant location is (-0.1, 0.6).
There is an infinity of possible locations.
The equidistant location is (5.5, 8.7).
The equidistant location is (5.4, 1.9).
The equidistant location is (168.8, -668.9).
The equidistant location is (1.0, 0.9).
The equidistant location is (0.9, 0.5).
There is no possible location.
The equidistant location is (1.2, 0.3).
The equidistant location is (-2.6, 2.6).

S

[Meng-Hsuan Wu]

0.3 0.5 0.0 0.9 0.2 0.8
The equidistant location is (-0.1, 0.6).

Thank for this test case! I finally got AC.

Meng-Hsuan Wu

[_.B._]

That's one really critical Input:

0.3 0.5 0.0 0.9 0.2 0.8

Will see why I get The equidistant location is (-0.1, 0.5).

Muito obrigado Sergio!

[_.B._]

Greetings!
Finally I got it ACed in Pascal
If it can help others, here is what I did:

To find if 2 slopes where approximated the same:
[pascal]SameSlopes:=abs (Slope1 - Slope2) < 1E-14;[/pascal]

To round it rigth:
[pascal]if abs(frac(Y) - 0.55) < 1E-8 then
Y:=Y+0.01;
if abs(frac(X) - 0.55) < 1E-8 then
X:=X+0.01;[/pascal]

And finally, to eliminate the -0.0 values:
[pascal]if abs(X) < 0.05 then
X:=abs(X);
if abs(Y) < 0.05 then
Y:=abs(Y);[/pascal]

The format to write the Real Type numbers:
[pascal]writeLn('The equidistant location is (',X:0:1,', ',Y:0:1,').')
[/pascal]

My I/O:

Input:

Code: Select all

24
0.0 1.0 0.0 3.0 1.0 2.0
0.0 -1.0 0.0 3.0 0.0 2.0
0.0 -1.0 0.0 -1.0 0.0 2.0
0.7 1.0 0.9 0.2 0.1 0.2
0.3 0.4 0.3 0.4 1.1 0.7
2.1 23.4 5.9 0.3 4.5 -2.0
1.0 0.0 0.2 0.8 0.1 0.9
8.2 -1.7 5.4 3.0 -4.0 15.1
7.2 3.5 5.2 9.3 0.7 8.2
-7.2 -3.4 6.3 9.7 -9.0 5.4
1.9 8.4 0.4 1.9 0.4 1.9
8.1 -0.2 0.5 1.9 2.3 2.4
6.0 4.3 2.9 0.1 -4.4 6.7
0.6 1.2 0.6 1.2 7.8 1.4
0.3 0.5 0.0 0.9 0.2 0.8
0.4 1.0 1.4 0.6 0.4 1.0
1.7 0.7 12.5 3.2 0.1 15.7
3.3 4.6 2.3 0.5 2.2 3.1
333.6 1.4 0.8 0.6 2.0 0.9
1.3 1.9 0.1 1.4 0.0 0.7
0.0 0.7 1.6 1.0 0.1 0.1
0.2 0.6 1.9 5.7 2.1 6.3
0.8 1.1 0.3 0.3 1.6 1.1
0.8 1.1 0.2 5.0 0.6 0.7

Output:

Code: Select all

The equidistant location is (0.0, 2.0).
There is no possible location.
There is an infinity of possible locations.
The equidistant location is (0.5, 0.5).
There is an infinity of possible locations.
The equidistant location is (-11.5, 9.3).
There is no possible location.
The equidistant location is (-65.7, -42.6).
The equidistant location is (3.7, 5.5).
The equidistant location is (0.0, 2.7).
There is an infinity of possible locations.
The equidistant location is (3.0, -3.7).
The equidistant location is (0.7, 5.0).
There is an infinity of possible locations.
The equidistant location is (-0.1, 0.6).
There is an infinity of possible locations.
The equidistant location is (5.5, 8.7).
The equidistant location is (5.4, 1.9).
The equidistant location is (168.8, -668.9).
The equidistant location is (1.0, 0.9).
The equidistant location is (0.9, 0.5).
There is no possible location.
The equidistant location is (1.2, 0.3).
The equidistant location is (-2.6, 2.6).

Hope it all helps!

Keep posting!

[tat tvam asi]

helo

anyone who dont like problems involving floating point
numbers ( like me ), can try the following:
read and treat the coordinates as whole numbers,
multiply them by ten. in so doing coincidence of points and collinearity can be tested with integer comparisons. i only used eps=0.00001 for the case of "real" triangle:

Code: Select all

            if ( ( ( x - 0.05 ) < EPS ) && ( ( x + 0.05 ) > EPS ) ) 
               x = 0.0 ;
            else
            {
               if ( x < EPS )
                  x -= EPS ;
            }

wher x is the first coodinate of the final result.
in my implementation int is not enough.

good luck
csaba noszaly

[Observer]

Hi there. Finally got AC with both codes! Thanks a lot~