## 270 - Lining Up

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

### Problem 270 - Runtime Error (SIGSEGV)

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
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:
I found my mistake, now its accepted.
Thanks for ALL the help.

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

### seek help!

can you tell me why Runtime Error (SIGSEGV)?

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

### Re: the problem is 270

the problem above is 270

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm
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
Time makes a fool of memory
And yet my memories still shine

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

### to obayashi

i will do as you say.
Thanks..

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 270 Is O(n^2) possible?

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 HATE testing account.
• Don't send me source code for debug.

thorgal
New poster
Posts: 1
Joined: Thu Aug 15, 2002 3:19 pm
Location: Stuttgart / Germany
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
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

### 270 RE

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
Hi

Should i read every data char by char??

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
ok thx

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### #270: 700 or more?

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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?