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 (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 1.3. Choosing Correct Numeric Data Types
 1.3. Choosing Correct Numeric Data Types | Reply
 Re: 1.3. Choosing Correct Numeric Data Types (response to post by Nickolas) | Reply Discussion continuedFindTriangle (floating-point imprecision)The evident approach for this problem is to use Heron's formula for calculating triangle's area. However, this is wrong: due to floating-point imprecision this formula returns non-zero area for some triangles with collinear vertices. A much safer way to calculate triangle's area is via cross-product of vectors representing its sides (see recipe "Using Vector Operations" for details). Finally, since coordinates of vertices are integer, the area will be an integer divided by two. To avoid comparing floating-point areas, we can store and compare twice-areas and divide the maximal of them by 2 only when returning it.Aircraft (floating-point imprecision + integer overflow)This is a nice example of a problem in which both types of error can occur. See recipe "Working with Lines and Segments" for analyses and solution.It is often helpful to do as many of your computations as possible in integers, switching to floating-point numbers only when it's really necessary. Thus, if you compare Euclidean distances between integer points, you can work with squared distances (which are integers) and extract square root only at the very end. Similarly, in PerforatedSheet you should calculate both total mass and weighted sum of rectangle center positions (multiplied by 2 again) in 64-bit integer, and postpone the division to the last step.See AlsoRecipe "Working with Numbers" for details on representation of integer and floating-point numbers.Recipe "Using Rational Arithmetic to Avoid Floating Point Imprecision" for another way to avoid floating-point imprecision.
 Re: 1.3. Choosing Correct Numeric Data Types (response to post by Nickolas) | Reply Some thoughts about numeric types are posted here.
 Re: 1.3. Choosing Correct Numeric Data Types (response to post by syg96) | Reply Borrowed your comment about using proper primitive data types, thanks. We'll probably remove this tip and the one about integer division from that recipe, since they are covered in this one.
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 1.3. Choosing Correct Numeric Data Types Previous Thread  |  Next Thread