Page 1 of 4

Problem 270 - Runtime Error (SIGSEGV)

Posted: Sat Jul 20, 2002 7:10 pm
by AlexandreN
Can anybody explain me why there are so many run time errors with that problem. (Including my ten ones) ? :evil:

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 ?

Posted: Mon Jul 22, 2002 3:16 pm
by AlexandreN
I found my mistake, now its accepted.
Thanks for ALL the help. :(

seek help!

Posted: Thu Aug 08, 2002 7:46 am
by liusu
can you tell me why Runtime Error (SIGSEGV)? :cry:

Re: the problem is 270

Posted: Thu Aug 08, 2002 7:48 am
by liusu
the problem above is 270 :oops:

Posted: Sat Aug 10, 2002 3:19 pm
by obayashi

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

to obayashi

Posted: Sun Aug 11, 2002 5:46 am
by liusu
i will do as you say.

270 Is O(n^2) possible?

Posted: Mon Aug 12, 2002 6:52 pm
by ..
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!

Posted: Thu Aug 15, 2002 3:35 pm
by 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?

270 RE

Posted: Fri Sep 20, 2002 6:59 am
by 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.

Posted: Fri Sep 20, 2002 8:12 am
by 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

Posted: Mon Dec 09, 2002 7:08 pm

Should i read every data char by char??

Posted: Tue Dec 10, 2002 9:06 am
by 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

Posted: Tue Dec 10, 2002 12:44 pm
ok thx

#270: 700 or more?

Posted: Mon Mar 10, 2003 9:10 am
by 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?

Posted: Sun Jan 04, 2004 9:57 am
by 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?