| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | wa 6,9,11,12 | Ade | 1265. Зеркало | 15 июн 2023 18:38 | 1 | no good epsilon for this problem
use big integers. | | Warning and Test 5 | Igor Parfenov | 1265. Зеркало | 2 июн 2023 02:40 | 1 | Do not believe the simplicity of the task at first glance. This is NOT a geometry problem. This is a "precision" problem.
Also, I misunderstood problem a little. If the second point is in front of mirror, but can not be seen in it, it is INVISIBLE. It is checked in test 5.
Input
7 2
5 3
1 3
4 4
Output
INVISIBLE | | hint | ASK | 1265. Зеркало | 24 апр 2018 16:37 | 1 | hint ASK 24 апр 2018 16:37 Do not fight with precision, use fractions in Python 3. | | Several data to KILL your program with PRECISION problems. | 198808xc | 1265. Зеркало | 4 май 2017 17:37 | 4 | BTW: I have used self-implemented high-precision longint to solve this problem.
1000 0 0 -1000 0 0 1000 1000
VISIBLE
1000 -0.000001 0 -1000 0 0 1000 1000
INVISIBLE
1000 0 -0.000001 -1000 0 0 1000 1000
INVISIBLE
1000 0 0.000001 -1000 0 0 1000 1000
VISIBLE
1000 -0.000001 0.000001 -1000 0 0 1000 1000
VISIBLE
1000 -1000 999.999999 -1000 0 0 1000 1000
INVISIBLE
1000 -1000 999.999999 -999.999999 0 0 1000 1000
VISIBLE
-999.999999 -1000 1000 999.999999 0 0 1000 1000
VISIBLE
1 2 1 0 0 0 0 1
VISIBLE
1.000001 2 1 0 0 0 0 1
VISIBLE
0.999999 2 1 0 0 0 0 1
INVISIBLE
1000 0 1000 -0.000001 0 0 0.000001 1000
VISIBLE
1000 0 1000 -0.000002 0 0 0.000001 1000
VISIBLE
1000 0 1000 -0.000003 0 0 0.000001 1000
INVISIBLE 2 more test which help me get AC, I fails on checking that both points on 1 side of line.
40 60 59 40 50 30 90 70
VISIBLE
40 60 61 40 50 30 90 70
INVISIBLE | | dont understand really | Igor Mihajlovic | 1265. Зеркало | 29 май 2015 14:26 | 2 | i dont understand this in 2d space
what about z coordinate
plz help | | What answer? | OpenGL | 1265. Зеркало | 14 май 2015 00:58 | 3 | What answer on this test?
0 3 1 1 1 0 3 0
Edited by author 04.01.2009 19:53 On C++ with double I got WA 9, on Pascal with extended - WA 4, but on Pascal with double - WA 11. Why???
Edited by author 04.01.2009 19:55 | | Description of solution for all and for WA#9! /// I DID IT!!! It's my 200'th problem)) And how I have 666 rank =)))) | Leonid (SLenik) Andrievskiy | 1265. Зеркало | 25 дек 2014 07:51 | 2 | I DID IT!!! It's my 200'th problem)) And how I have 666 rank =))))
----------
Preamble.
I've just solved this problem in C# using only Double type (64-bit floating point) and using only operations: +, - and *.
My method also can be used with only integer numbers. But in that way you'll need to code 128-bit signed integer type.
You have 4 points: "the banker’s eye" [name it Eye], "the victim" [name it Victim], "first mirror coordinate" [name it Mirror1], "second mirror coordinate" [name it Mirror2].
At first you should check whether Eye and Victim are in one halfplane relative to the mirror line. If they are not, then answer is INVISIBLE.
And now starting the most interesting part of solution.
My first thought was to build mirrored lines of sight (first: see from Eye, refraction point is Mirror1; and second: see from Eye, refraction point is Mirror2) ans check whether Victim is between that mirrored lines of sight.
But it requires more precision than double can offer.
And then I understand that there's another way to solve that problem!!
Hint1:
Build an equation, that depends of Eye, Victim, Mirror1, Mirror2, and RefractionPoint.
The last parameter is some point on the line formed by Mirror1 and Mirro2 points.
This equation must be true if the angle of incidence (between Eye and mirror) equals to the angle of reflection (between Victim and mirror) in RefractionPoint.
The only operation you need is +, -, * and /. But if you dispose of division and move all to the left side of the equation you'll get a function that equals to 0 when the angle of incidence equals to the angle of reflection in RefractionPoint and not equal to 0 otherwise.
Hint2:
The fact about that function: the sign of its returning value can say you a direction where to find that point.
And the last hint:
The jury do not ask you to find the refraction point =) They only ask you to determine if Victim is seen from Eye (!!!!). In other words "is there exists a RefractionPoint between Mirror1 and Mirror2 that function we've built equals to 0 in that point?"
Well, I think it is enough to solve this problem =))
Edited by author 20.07.2011 03:15 | | wa #9 (+) | AlMag(VNTU) | 1265. Зеркало | 27 окт 2011 18:55 | 8 | I have only ONE division and no sqrt's, no rotates! what's wrong? Try rewrite program on pascal with extended. I got wa9 on C++ too, but on pascal same algo got AC
Edited by author 10.04.2009 12:56 ok, i'll try. but why? i used long double, is that correct? sizeof (long double)=sizeof (double) Try to swap(x1,x2) and swap(y1,y2). This change gave me AC. thanks, it's really weird..... | | Test#26 | Yusupov Azat(UB of TUIT) | 1265. Зеркало | 12 ноя 2010 16:16 | 1 | Test#26 Yusupov Azat(UB of TUIT) 12 ноя 2010 16:16 In the test #26 banker’s eyes and (x2,y2) points are situited in the opposite sides of the mirror.
Answer should be "INVISIBLE". | | Does anybody have test#3 - WA!!! | Valentine | 1265. Зеркало | 31 авг 2010 19:55 | 4 | 2 -2
0 4
0 0
2 2
ans = INVISIBLE It is not test 3. I get WA3 whith ans INVISIBLE 0 -1
2 -1
2 0
0 0
answer: visible | | Precision | Borisov Nikita | 1265. Зеркало | 19 июн 2008 22:19 | 2 | I think it's terrible problem. I've used diffrent eps to solve it.
And than I change it to eps = 0... I couldn't belive my eyes.... It was AC. So, if you have a lot of strange WA's, try not to use eps. Thanks, it really helped me :) | | C and Pascal | Burunduk1 | 1265. Зеркало | 13 апр 2007 17:25 | 9 | There are 2 same solutions (C, Pascal).
C solution gets WA, 9
Pascal solution gets AC
Why??? Please, give me some hints about it. For example (sizeof(long double) == 8) I thought it's so only in Visual C.
GNU C and Borland C compilers use sizeof(long double) = 10.
Am I right? Yes.
But as far as I know Intel C++ compiler is used there. And in ICL (at least in 8.1) sizeof(long double)==8 Of course!
But solution without it is more short and beauty. :)
And it's more interesting to solve problem
using only Extended. But if juri suppose exact numbers
when answer is unequivocal it would be funny
try adjust eps-heuristics. Next time you would be killed by
rejujement.
I have Ac using 120-digits integers and dot-product as angle haracteristics. Thus use only +,-,*,<,==. My program doesn't use any long arithmetics - only standard Pascal's real (or extended?) type, and it hasn't any problem with accepting this problem. If jury assumed using long arithmetics, then testset is very weak... Could anybody say me how find point, symmetrical to given point relatively some line?
Without division...
Thanks | | !!!....I have some questions...!!! Please help me.... | ZiV | 1265. Зеркало | 21 янв 2006 14:55 | 3 | I'm sorry....
В условии сказано "Гарантируется, что точки (x1, y1) и (x2, y2) не лежат на прямой, проходящей через точки (xm1, ym1) и (xm2, ym2)" Это значит что они одновременно не лежат или одна может лежать а другая нет?...
Edited by author 21.01.2006 13:51 Re: Someone 21 янв 2006 14:29 It means that each of these points doesn't belong to the line, passing through the points (xm1, ym1) and (xm2, ym2). Then i could not understand how this solution gets WA#23
Const
Eps = 1e-15;
function Eq(a, b : Extended) : boolean;
begin
Result := Abs(a-b) <= eps;
end;
Function Less(a, b : Extended): boolean;
begin
Less := Eq(a,b) or ((a - b) <= -eps);
end;
Function Less1(a, b : Extended): boolean;
begin
Less1 := ((a - b) <= -eps);
end;
Var
x1,x2,x3,x4,x5,y1,y2,y3,y4,y5 : extended;
A,B,C,A1,b1,c1 : extended;
BEGIN
Read(x1,y1);
Read(x2,y2);
Read(x3,y3);
Read(x4,y4);
x5 := 2*(y3-y4)*((x3-x4)*(y2-y3) - (x2-x3)*(y3-y4))/
( (x3-x4)*(x3-x4) + (y3-y4)*(y3-y4)) + x2;
y5 := 2*(x4-x3)*((x3-x4)*(y2-y3) - (x2-x3)*(y3-y4))/
( (x3-x4)*(x3-x4) + (y3-y4)*(y3-y4)) + y2;
A := y1-y5;
B := x5-x1;
C := -(A*x1+B*y1);
A1 := y3-y4;
B1 := x4-y3;
C1 := -(A1*x3 + B1*y3);
if (Less((A*x4+B*y4+C)*(A*x3+B*y3+C),0)) and ( Less1((a1*x1+b1*y1+c1)*(a1*x5+b1*y5+c1),0)) then
Writeln('VISIBLE')
Else
Writeln('INVISIBLE');
END.
Edited by author 21.01.2006 19:32 | | WA#26! Why? | Vedernikoff Sergey | 1265. Зеркало | 16 авг 2005 02:57 | 1 | | | AC!I think it is a good maths problem:) | Yu Yuanming | 1265. Зеркало | 2 июл 2005 14:24 | 1 | At first,I use line equation, I assume perc = 1e-6, WA#6...
and then prec = 1e-12, WA#9...:(
It seems that the prec is terrible...
Finally, I found that uses vectos with some calculate improvement, it needs only add, sub, mul...
Just maths jobs...
It can AC easily:) | | Troubles with Precision | wwwwww | 1265. Зеркало | 13 май 2005 02:40 | 1 | My solutions get WA 8 and WA 13. (It doesn't use long numbers)
I'm sure it's so because of precision.
If you have solution without long 100-digit numbers,
send me please to sk1@hotbox.ru
| | WA #8 | Lightweight! Lightweight baby! | 1265. Зеркало | 24 сен 2004 20:31 | 9 | WA #8 Lightweight! Lightweight baby! 10 авг 2004 03:12 I get WA #8 and I suppose it's because of the precision.
I tried rotating everything so that the mirror becomes (0,0) -> (L,0) actually using sin and cos and got WA #8.
I tried finding out the relative coordonates without actually using rotations (using distances) and got WA at even lower tests (4 or 5).
Can anybody help me with some hints? Should i try it in pascal with the extended type? Or anybody that got AC in C please help. All calculations can be done in integers. 100-digit numbers are quite enough. But don't you need sqrt (and maybe division too)? Or you did those on large numbers as well? I don't need division and sqrt, only addition, subtraction and multiplication. I tried using double and no rotations. Actually the exact operations i did on long nombers and got AC, but on double (only add, sub and mul). It didn't work. Maybe with pascal's extended it does. How? Maigo Akisame (maigoakisame@yahoo.com.cn) 15 сен 2004 20:15 |
|
|
