I solved 270 by an algorithm of O(n^2 lgn).
But in the ranking, there are someone solved it in 1, 2 seconds.
Is there any O(n^2) algorithm for this question??
Thanks a lot!
My signature:
Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
I keep on getting Runtime Error. How do I deal with this multiple input problem? Do I just write a program for one input, and the judge will run my program multiple times?? Or do I write a program to handle multiple inputs?? Please explain.
If problem has blue mark, you must handle multiply input SELF.
In the past judge runs our programs many times if program have more than one input file - i.e. 111 problem. But now they discovered blu mark and we must handle such kind of data
In this problem you have to read number of tests and after that, read all tests to the end of file or number of tests. Test's data are separeted by empty lines.
Can either of you explain your algorithm or give more hints?
Here is my take:
1) Hash all coordinates by x and y values to arrive at 2 hash tables, one for x and one for y values.
2) Take the hash table (either x or y) with the least hashes.
3) Compare all coorindates in a hash with all coordinates OUTSIDE the hash (since every coordinate in a hash forms either a vertical or a horizontal line, so that is a trivial solution).
4) To see if three points a, b and c are collinear, (a is in the hash, b and c are outside the hash), simply compare the gradients of a-b and a-c.
My algorithm to compare the gradients is simply for all points outside a hash, calculate the gradient with a point inside the hash. If any two gradients are simliar, then the 3 points are collinear.
This, however, is a O(n^3) algorithm and even when I hash the gradients for each point, I get time limit exceeded.
Am I on the right track here, or am I hashing the wrong things altogether?
there is a way to solve this problem in O(n^2).
Is problem description correct?