mI thought that, in order to solve this problem, we'd have to take one line segment (the ship) and take N others line segments (the asteroids) and calculate how many of these N line segments intersect the first line segment (the ship)...
Is it correct?
Iis there some trick in this problem?
This is exactly what You need to do!
but why i have for 5 tests messege wrong result
marveringius also have same situation
Hmmm, but I used some algorithm that I've already used for other problems and I didn't get 100%.. Maybe I'm misinterpreting something in my code..
now i sow my mistake i use %d in printf function instead of %ld for long int at end result such stupid mistake....
But is this a problem? The maximum value for N is 750.000 so your int can hod this value...
i dont know but i think that int is from -32000 to 32000 i do simple test on my pc and for %d in printf function for number larger then 32000 i have crayz result,i am sure that algorithm is good i think someone need to check yours and mine code
This interval is for short... In most computers int has 32 bits and this is -2^31, 2^31 - 1
2^31 - 1 is more than 1 billion..
I think my code is correct too because I used an algorithm already tested by others.. Maybe we are making mistakes in another part of the code...
Why can't I access the problem yet?
Only 6 persons got this problem... I saw some possible mistakes on my code.. I will wait for the problems to be in the practice to test my modified code...
i know that but i said that i do simple test on my pc and get that problem,long int is from -2 147 483 648 to 2 147 483 647 something like that
long int here in my pc is from -2147483648 to 2147483647... that's strange...
Aaah, you edited the topic, heheheh
do you know when can we use the problems??
but mistake in my program is becose i use bad conversion i used &d instead of %ld i think this is mistake,but strange thing that we have mistake on identical tests
i dont know this is first time i submit my code
I'm waiting here to test my code that I modifiied....
Segments which represent Ship and Asteroids can be in various position among themselves. You must check all of it.
Well i don't understand too why i became WA. I solved the problem with vector produkt. I expected TL . . .
What's with the huge input for this task?
I can't get past time limit with just reading the input with scanf. It's kind of annoying. :/
Same here, How could it be WA> I used segment intersection with vector produkct in O(n).
Vector product requires a lot of multiplication operations so when you take into consideration the fact that you're working with 32 bit integers... It's a lot of work, I suppose.
Proper implementation of vector product segment intersection cleans 80% of the task with 2 last cases hung out on TLE.
My guess here is sweep line, in order to pass the last two cases. But, I'm not sure... It would ask storing all the values first in some structure (probably RB-tree or AVL) and than running mentioned algorithm.
Am I right?
I used the algorithm for line segments intersection that is at the famous book from Sedgewick....
I took the line segment (x0,y0) (x,y) from the ship and tested it against all line segments (a0,b0)(a,b) from the asteroids.. I got TLE for 2 cases and WA for 4 cases.. TLE is acceptable but WA, I don't think so since I was using some kind of algorithm from a textbook....
Maybe, I'm not seeing something wrong in another part of my code...
@marveringius:
Well that i asked myselft too...
I solved it with a famous algorithm
( vector produkt method ), and expected TL, but I became WA too :S
Can someone (that solved this problem) see our algorithm and help us??
Something very strange happened:
I used this algorithm: read all the input (using scanf()) and do nothing (that is, return 0).
And the result was:
Test 8 Time limit exceeded
Test 9 Time limit exceeded
I remember that during the contest I asked in the forum if we can read 4*750.001 double within the time limit and someone told me that he did it with 0.3 seconds.
For the cases 8 and 9, two seconds were not enough only to read the input. I'm curious now to know where is the trouble...
Z-trening sometimes says it is time limit but it was that you used too much memory space .
You can tTry to read all input in only 4 variables and tell us is that an error.
Ok, I did it.. This time I only used 1 int to read the n segments and 4 double to read the input... I had the same result.. TLE for 2 cases and 1 case almost TLE (1,64 seconds).
i have same problem like you i also used famos algorithm and like you get tl in 2 cases and wa in 4 cases it is really strange problem i dont know where we made mistake
And what about the problem with the input?
I'd like to know from the author of this problem what's happening because I did a program that only read the input and exit and I got TLE for 2 cases and one case I almost got TLE...
This is PASCAL Vs C++ collision.
I believe that author work in PASCAL and he set up Time limit accordingly to his code. So this time C++ programmers have problems with last 3 cases. Still solvable in C++ with some faster inputs but really not for this level of competition.
More task are better suited for C++ programmers. So this one gone in PASCAL favor.
"This things" happens. So accept our apologize for this failing to balance task between Pascal and C++. We will have this case in mind for next competitions.
Ok, no problem. I was only wondering what was happening... =)
But pascal reads double well faster than C's scanf()?
Well I'm more interested in why I become WA , and not in TL . . .
Maybe this can help. Try to recheck this part of code:
else if( s1==0 && S1.ON_LINE(S2.A) )return 1;
else if( s2==0 && S1.ON_LINE(S2.B) )return 1;
else if( s3==0 && S2.ON_LINE(S1.A) )return 1;
else if( s4==0 && S2.ON_LINE(S1.B) )return 1;
with
fabs(s1) < error
in all conditions, where error is some small value.
If x is real expressions it is rare that You can have x == 0.
You can write your own fuctions for input of floats, using chars. Instead of scanf, use getch(). I did that and passed all tests... And if you get WA, make sure you considered that some lines can be points, and paralel lines coliding...
Thanks everybody.. I'll try it later.. I have some things to do now but later I come back to try this "real numbers way of read", hehehe
Thanks again.. =)
Thanks but I know that. I've learned C before C++ so I know these functions.. ;)
I know that conio.h is not from the standart C.
Can I have the 4th test case? Thanks
Can't find bug though :S
