270 - Lining Up

[AlexandreN]

Can anybody explain me why there are so many run time errors with that problem. (Including my ten ones) ?

I think that this problem is very easy, but I always get Runtime Error.

Since this is a multiple input problem, I supose that the input is as follow.

2 //Number of test cases
//blank line
1 1
2 2
3 3
9 10
10 11
//blank line
1 1
2 2
3 3
4 4
5 5

Is this correct ?

[AlexandreN]

I found my mistake, now its accepted.
Thanks for ALL the help.

[liusu]

can you tell me why Runtime Error (SIGSEGV)?

[liusu]

the problem above is 270

[obayashi]

SIGSEGV means

SIGnal of SEGment Violation

it often occurs when referring to invalid memory
eg. the subscript of the array exceeds the range what it should be within.

check your code carefully and think more over about where it is likely to happen.

good luck

[liusu]

i will do as you say.
Thanks..

[..]

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!

[thorgal]

Yes there is a way to solve this problem in O(n^2).
By now I give you a little hint: hash table.
Can you now find a solution of this time complexity?

[jingye]

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.

[Dominik Michniewski]

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.

Best regards
Dominik

[PMNOX]

Hi

Should i read every data char by char??

[Dominik Michniewski]

It's your choice ....
It's strongly depend which problem do you want to solve ...

In many problem you could read data by scanf() or gets() and sscanf() ...
But in some of problems is better to read data char by char )

Best regards
Dominik

[PMNOX]

ok thx

[minskcity]

Problem description states

The input consists of N pairs of integers, where 1 < N < 700

But after submitting a couple solutions I doubt about it... Is problem description correct?

[junbin]

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?