Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 2012-01-26 08:29:40
- anonimnystefy
- Real Member
- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,049
A programming question!!!
hi guys
You are given a set of points {(x1, y1), (x2, y2), ..., (xn, yn)}. You should compute the smallest menhetn distance between all the pairs of the points.
Menhetn distance between two points (a, b) and (c, d) is defined as |a - c| + |b - d|.
INPUT:
In the first line of the standard input is given an integer n (2 <= n <= 1000). In the next n lines are given the points -- in the i-th is given the point (xi, yi) (-100000 <= xi, yi <= 100000), where both xi and yi are integers.
OUTPUT:
In the first and the only line of the standard output you should print the smallest distance.
Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.
Offline
#2 2012-01-27 03:59:58
- John E. Franklin
- Member
- Registered: 2005-08-29
- Posts: 3,588
Re: A programming question!!!
So menhetn distance as anoni has mentioned would be like walking along blocks in a big city, you can't go diagonally,
but only follow x and y to get there and then compute the distance. Very simple, much easier, no pythagoean theorem.
igloo myrtilles fourmis
Offline
#3 2012-01-27 04:00:59
- John E. Franklin
- Member
- Registered: 2005-08-29
- Posts: 3,588
Re: A programming question!!!
I suppose this could be similar to Manhattan distance?
igloo myrtilles fourmis
Offline
#4 2012-01-27 04:22:56
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: A programming question!!!
Hi;
Yes, he means manhattan distance.
Take and form two loops to generate all possible pairs and then use the formula for manhattan distance on each pair. Use one variable as the holder for the smallest found so far.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#5 2012-01-27 05:50:14
- anonimnystefy
- Real Member
- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,049
Re: A programming question!!!
hi bobbym
that was my first thought,but it takes more time than it should.is there a relation that calculates the minimum Manhattan distance of three points?maybe then i can expand it for more points.
Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.
Offline
#6 2012-01-27 05:54:47
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: A programming question!!!
I disagree, you are asked to find the smallest from all possible pairs of points. How can that be expanded?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#7 2012-01-27 06:38:06
- anonimnystefy
- Real Member
- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,049
Re: A programming question!!!
yes,but i meant that maybe there's a formula that calculates that minimum distance for 3 points.then it could be used for the task.
Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.
Offline
#8 2012-01-27 06:43:46
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: A programming question!!!
Not without trying each pair of points. Let's assume such a formula exists. For two points it has 2 variables for 3 probably 3 variables for 10000 points maybe 10000 variables. I do not think it has been discovered.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#9 2012-01-27 07:10:23
- anonimnystefy
- Real Member
- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,049
Re: A programming question!!!
no,i just need for three.
Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.
Offline
#10 2012-01-27 08:03:01
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: A programming question!!!
Okay, you have lost me. Three what?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#11 2012-01-27 08:25:00
- anonimnystefy
- Real Member
- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,049
Re: A programming question!!!
three points.i just want some way to find the minimum Man. distance for three points.
Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.
Offline
#12 2012-01-27 08:32:48
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: A programming question!!!
I doubt that there is anything simpler than trying all 3 pairs of points. At least I have never heard of it.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#13 2012-01-27 12:56:45
- John E. Franklin
- Member
- Registered: 2005-08-29
- Posts: 3,588
Re: A programming question!!!
Yeah, just try all three like this in BASIC:
jFinished = 18
abs(ax - bx) + abs(ay - by) = mAB
abs(ax - cx) + abs(ay - cy) = mAC
abs(bx - cx) + abs(bx - cy) = mBC
''find the smallest of the three
if (mAB = mAC) then
if (mAB = mBC) then
print "All three distances are the same and are: ";mBC
jFinished = 22
end if
end if
if (18 = jFinished) then
if (mAB = mAC) then
if (mBC < mAB) then
print "distance BC is the smallest and is: "; mBC
jFinished = 22
else
print "distance AB and AC are the smallest and are equal and are: "; mAB
jFinished = 22
end if
end if
if (mAB = mBC) then
if (mAC < mBC) then
print "distance AC is the smallest and is: "; mAC
jFinished = 22
else
print "distance AB and BC are the smallest and are equal and are: "; mAB
jFinished = 22
end if
end if
if (mAC = mBC) then
if (mAB < mBC) then
print "distance AB is the smallest and is "; mAB
jFinished = 22
else
print "distance AC and BC are the smallest and are equal and are: "; mBC
jFinished = 22
end if
end if
end if
'''comment: All 3 distances are different below here.
if (18 = jFinished) then
if (mAB < mAC) then
if (mAB < mBC) then
print "distance AB is the smallest and is: "; mAB
jFinished = 22
end if
end if
if (mAC < mBC) then
if (mAC < mAB) then
print "distance AC is the smallest and is: "; mAC
jFinished = 22
end if
end if
if (mBC < mAB) then
if (mBC < mAC) then
print "distance BC is the smallest and is: "; mBC
jFinished = 22
end if
end if
end if
if (18 = jFinished) then
print "Something is wrong with the program or the software."
end if
''(end of file)
''EOF
Last edited by John E. Franklin (2012-01-27 12:58:18)
igloo myrtilles fourmis
Offline
Pages: 1