bisection or something else..
Moderator: Board moderators
bisection or something else..
given the cartesian coordinates of three points A, B and C...
find a point D such that dis(A,D) + dis(B,D) + dis(C,D) is minimum..
where dis(a, b) is the euclidian distance between point a and b.
what is the approach to solve this kind of problem?
find a point D such that dis(A,D) + dis(B,D) + dis(C,D) is minimum..
where dis(a, b) is the euclidian distance between point a and b.
what is the approach to solve this kind of problem?
yeah you are right .
how about this one
let Pab = middlePoint(A,B)
let Pac = middlePoint(A,C)
let Pbc = middlePoint(B,C)
Pab, Pac, Pbc can be candidate of D.
after that :
E = Pab, F=Pac, G=Pbc
let Pef = middlePoint(E,F)
let Peg = middlePoint(E,G)
let Pfg = middlePoint(F,G)
Pef, Peg, Pfg can be candidate of D.
repeat this procedure until the new three point are not same each other.
I think this method can give the better result from my last post.
I only try to help
how about this one
let Pab = middlePoint(A,B)
let Pac = middlePoint(A,C)
let Pbc = middlePoint(B,C)
Pab, Pac, Pbc can be candidate of D.
after that :
E = Pab, F=Pac, G=Pbc
let Pef = middlePoint(E,F)
let Peg = middlePoint(E,G)
let Pfg = middlePoint(F,G)
Pef, Peg, Pfg can be candidate of D.
repeat this procedure until the new three point are not same each other.
I think this method can give the better result from my last post.
I only try to help
"Life is more beautiful with algorithm"
This is called the Steiner point (of a triangle), try feeding that into Google.
If I recall correctly, if the triangle has an angle larger than or equal to 120 degrees, then the answer is the vertex with the large angle. Otherwise it is a point in the interior of the triangle such that all three angles ADB, BDC and CDA are equal to 120 degrees.
(Edit:) If this is correct, one can find the answer in the second case by computing the intersection of two circle arcs (the set of points E such that angle AEB has 120 degrees is a union of two such arcs).
BTW, I think I saw this task in the past "Timus Top Coders" contest (although I didn't solve the contest). Is this where you have it from?
If I recall correctly, if the triangle has an angle larger than or equal to 120 degrees, then the answer is the vertex with the large angle. Otherwise it is a point in the interior of the triangle such that all three angles ADB, BDC and CDA are equal to 120 degrees.
(Edit:) If this is correct, one can find the answer in the second case by computing the intersection of two circle arcs (the set of points E such that angle AEB has 120 degrees is a union of two such arcs).
BTW, I think I saw this task in the past "Timus Top Coders" contest (although I didn't solve the contest). Is this where you have it from?
thanks.. i googled for a bit and found the answer.
http://mathworld.wolfram.com/FermatPoints.html
The problem is also called Fermat Point.
http://mathworld.wolfram.com/FermatPoints.html
The problem is also called Fermat Point.
Yes.misof wrote: BTW, I think I saw this task in the past "Timus Top Coders" contest (although I didn't solve the contest). Is this where you have it from?

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
Another harder version exists in Dhaka regional 2002, although both may have small floating point problem.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Another related problem is http://acm.uva.es/p/v102/10228.html
But there you have N<=100 points, instead of just 3.
But there you have N<=100 points, instead of just 3.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
First of all these problems appeared in Online contests other than the Dhaka regional one. So it was ok.
It can be a debate on whether something is a trivial knowledge on a nontrivial one. Someone weak in graph problems can argue that matching problems are nontrivial, some one weak in number theory may argue that pick's theory is a nontrivial thing but both of them appear in contest So there is no point in making such arguments. Problems that require special knowledge appear in contests and will continue to appear.
Someone can say that those things taught in undergraduate level is trivial. But I can't remember any course that taught matching or pick's theorem. May be some better universities do teach them. So the inconsistency is there and so is the argument.
It can be a debate on whether something is a trivial knowledge on a nontrivial one. Someone weak in graph problems can argue that matching problems are nontrivial, some one weak in number theory may argue that pick's theory is a nontrivial thing but both of them appear in contest So there is no point in making such arguments. Problems that require special knowledge appear in contests and will continue to appear.
Someone can say that those things taught in undergraduate level is trivial. But I can't remember any course that taught matching or pick's theorem. May be some better universities do teach them. So the inconsistency is there and so is the argument.
I learned about bipartite matching the second year in university, both through a discrete math class and an algorithms class.
Pick's Theorem I would consider more "special" knowledge. Though I guess if you study pure math and mainly combinatorics you might hear about it already as an undergrad.
(Even though I know both of them, I would not consider either of them to be "trivial" though.)
Pick's Theorem I would consider more "special" knowledge. Though I guess if you study pure math and mainly combinatorics you might hear about it already as an undergrad.
(Even though I know both of them, I would not consider either of them to be "trivial" though.)
Re: hmm
Actually, my post was more of a query than an argument. I am sorry, if I have given any false impression.shahriar_manzoor wrote:First of all these problems appeared in Online contests other than the Dhaka regional one. So it was ok.
It can be a debate on whether something is a trivial knowledge on a nontrivial one. Someone weak in graph problems can argue that matching problems are nontrivial, some one weak in number theory may argue that pick's theory is a nontrivial thing but both of them appear in contest So there is no point in making such arguments. Problems that require special knowledge appear in contests and will continue to appear.
Someone can say that those things taught in undergraduate level is trivial. But I can't remember any course that taught matching or pick's theorem. May be some better universities do teach them. So the inconsistency is there and so is the argument.
What I wanted to know, how most people solve these problems. Do they rely on their special knowledge or they use their intuition and skills to derive a solution. Of course, to do this, one would also require some knowledge, such as trigonometry and manipulation of equations. Now, considering the course contents of 12Grade, A' Level, HSC etc, someone who really understands the topics of their books, these things are trivial.
Although I learned many properties of triangles at High School, I don't remember anything like these. That is why I made the query.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
The problems I mentioned are solvable by some sort of bisection but still one has to have the 120 degree knowledge. So without some special knowledge these can be difficult to solve or may be there is I am not sure.
AFAIK Steiner tree problems are open problems but when there is only one hub it is not open.
In any case I slightly misunderstood your post as well. And also the cause of misunderstanding is on a previous occasion I was asked by you or your brother are questions requiring special knowledge fit for contests...
AFAIK Steiner tree problems are open problems but when there is only one hub it is not open.
In any case I slightly misunderstood your post as well. And also the cause of misunderstanding is on a previous occasion I was asked by you or your brother are questions requiring special knowledge fit for contests...