JOIN
 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 | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Marathon Matches Marathon Match 23 Post your approach
 Post your approach | Reply My basic algorithm has three stages:1) Find a point in the polygon2) Expand it to a triangle3) Pick a likely side and see if there is more polygon beyond itI mostly choose lines and do binary searches for the polygon boundary along those lines. For each vertex I create, I keep the in point (the closest one to the boundary that is inside the polygon) and the out point (the closest one outside the polygon). Everything is based around the fact that with a convex polygon, you can't have a line go from inside the polygon to outside and then back in. I use this to find the largest triangle that could have a given side of my current polygon as its base. I also use it to move my in and out points closer to the polygon boundary without using more queries (well, sometimes I query the midpoint if it seems the best thing to do).My code is available here: PolygonArea_jdmetz.cpp And it is pretty well commented.It gets 4.9842 on average over 100000 cases.