10697 - Firemen barracks

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by sergio » Thu Sep 02, 2004 3:49 pm

> 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
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Thu Sep 02, 2004 5:01 pm

I got AC now!

Thanks every one!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Sep 02, 2004 6:00 pm

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? :cry:
My solution is similar to that of 190 Circles through 3 pts... Needless to say, I get AC for that problem.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by sergio » Thu Sep 02, 2004 7:42 pm

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]

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Read the posts below this one :)

Post by _.B._ » Thu Sep 02, 2004 9:19 pm

Took me more than 20 submissiones to get it ACed.
I'm using FreePascal.
Read posts below for I/O.
Last edited by _.B._ on Fri Sep 03, 2004 6:37 pm, edited 1 time in total.
_.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Thu Sep 02, 2004 10:12 pm

sergio wrote:> 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
New poster
Posts: 5
Joined: Thu Aug 22, 2002 9:41 am
Location: Taiwan
Contact:

Post by Meng-Hsuan Wu » Fri Sep 03, 2004 1:34 am

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 :wink:

[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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Sep 03, 2004 5:01 am

sergio wrote: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.
sergio wrote:I can also post more test cases if you want.
Please do so~ :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll » Fri Sep 03, 2004 8:46 am

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

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by sergio » Fri Sep 03, 2004 3:46 pm

Meng-Hsuan Wu wrote: 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
New poster
Posts: 5
Joined: Thu Aug 22, 2002 9:41 am
Location: Taiwan
Contact:

Post by Meng-Hsuan Wu » Fri Sep 03, 2004 4:58 pm

sergio wrote: 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 :lol:

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Will work on it...

Post by _.B._ » Fri Sep 03, 2004 5:03 pm

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

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

ACed in Pascal.

Post by _.B._ » Fri Sep 03, 2004 6:33 pm

Greetings!
Finally I got it ACed in Pascal :D
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
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Sat Sep 04, 2004 11:39 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Sep 05, 2004 8:15 am

Hi there. Finally got AC with both codes! Thanks a lot~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 106 (10600-10699)”