JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Marathon Matches Marathon Match 23 Re: Post your approach Revision History (1 edit)
 Re: Post your approach (response to post by jdmetz) My strategy is based off a few theorems stemming from the fact that we are looking at a convex polygon (proofs are left to the reader):Let points inside the polygon be good points, all other points are bad pointsT1) Any point on the line segment AB, where A and B are good points, are themselves good (we shall call this a good segment)T2) The convex hull of a set of good points must also be good (we shall call this a good polygon)T3) There must be exactly one 'border' between a good point and a bad pointT4) (The major theorem) Given a good segment AB and a bad point C, draw two infinite rays starting from C in the direction of vectors AC and BC ...every point in the area between the two rays you just drew is also bad (including the rays themselves) <-- this allows rapid elimination of areasT5) (Another big one) Given a good segment AB on a good polygon, draw one infinite ray from any point on AB in a direction headed outward. There must be a border point somewhere on the ray (possibly on AB itself), after which all points are bad <--- this allows binary searchHow I used these could have been better, but anyway:1) Pick and test random points until you have three successful points.By far the weakest part of my algorithm...if I didn't find three points after N measurements, I did a variety of things, none of which worked well2) Repeat the following until N measurement overall have been done: a) Find the convex hull of all good points (using Graham scan) b) Take each vertex and find the area gain I would get if i extend that vertex out from the centroid. Take each midpoint of each side of the hull and extend it perpendicularly and see the area gain. Pick the point with the most possible area gain. c) call isInside with this point of maximal potential gain, update arrays of good and bad points3) (This led from 2444->2469) Now take the midpoints of each segment of the convex hull, and extend it perpendicularly one last time. Find the area of this new polygon. Return the average of the area of the new polygon and the convex hull (almost always the true area was somewhere in this range).4) (This stunningly led to 2469->2479) Take one or two thousand results....plug the real (not absolute differences) into Excel (not 2007!) and graph as a function of N. Fit a curve to the data (logarithmic worked well for me) and put the result (which is a function of N) as a fudge factor to your answer....5) (2479->2481) Return the weighted average between the smaller area and 6 times the larger area.Fudge, indeed, is yummy. I hope this is the start of a bunch of good marathons for me!EDIT: wow, my approach is somewhat similar to jdmetz's....except that I always include the midpoint in my deliberations as to which point to attempt an extension from, which is probably wasteful in some casesExample results:0) 4.9900479639285041) 4.99132262005329252) 4.9706961429254123) 4.99285532561848564) 4.9822725054002215) 4.9077824319352126) 4.9637372670203777) 4.9932544065615728) 4.9988686867331829) 4.981794885452505
 Re: Post your approach (response to post by jdmetz) My strategy is based off a few theorems stemming from the fact that we are looking at a convex polygon (proofs are left to the reader):Let points inside the polygon be good points, all other points are bad pointsT1) Any point on the line segment AB, where A and B are good points, are themselves good (we shall call this a good segment)T2) The convex hull of a set of good points must also be good (we shall call this a good polygon)T3) There must be exactly one 'border' between a good point and a bad pointT4) (The major theorem) Given a good segment AB and a bad point C, draw two infinite rays starting from C in the direction of vectors AC and BC ...every point in the area between the two rays you just drew is also bad (including the rays themselves) <-- this allows rapid elimination of areasT5) (Another big one) Given a good segment AB on a good polygon, draw one infinite ray from any point on AB in a direction headed outward. There must be a border point somewhere on the ray (possibly on AB itself), after which all points are bad <--- this allows binary searchHow I used these could have been better, but anyway:1) Pick and test random points until you have three successful points.By far the weakest part of my algorithm...if I didn't find three points after N measurements, I did a variety of things, none of which worked well2) Repeat the following until N measurement overall have been done: a) Find the convex hull of all good points (using Graham scan) b) Take each vertex and find the area gain I would get if i extend that vertex out from the centroid. Take each midpoint of each side of the hull and extend it perpendicularly and see the area gain. Pick the point with the most possible area gain. c) call isInside with this point of maximal potential gain, update arrays of good and bad points3) (This led from 2444->2469) Now take the midpoints of each segment of the convex hull, and extend it perpendicularly one last time. Find the area of this new polygon. Return the average of the area of the new polygon and the convex hull (almost always the true area was somewhere in this range).4) (This stunningly led to 2469->2479) Take one or two thousand results....plug the real (not absolute differences) into Excel (not 2007!) and graph as a function of N. Fit a curve to the data (logarithmic worked well for me) and put the result (which is a function of N) as a fudge factor to your answer....5) (2479->2481) Return the weighted average between the smaller area and 6 times the larger area.Fudge, indeed, is yummy. I hope this is the start of a bunch of good marathons for me!Example results:0) 4.9900479639285041) 4.99132262005329252) 4.9706961429254123) 4.99285532561848564) 4.9822725054002215) 4.9077824319352126) 4.9637372670203777) 4.9932544065615728) 4.9988686867331829) 4.981794885452505