My Weblog

Blog about programming and math

SPOJ 8670. THE MAX LINES

import Data.List
import Text.Printf
import Control.Monad
import qualified Data.ByteString.Char8 as BS

readN::BS.ByteString -> Integer
readN x = case BS.readInteger x of 
	   Nothing -> 0
	   Just ( t , _ ) -> t


main = do 
	n <- liftM readN ( BS.getLine )
	let fun x k | x > k = return () 
		    | otherwise = do 
				   m <- liftM readN ( BS.getLine )
				   printf "Case %d: %.2f\n"   x  (  fromIntegral  ( 4*m^2 )  + ( 0.25::Double ) )
				   fun (x+1) k 
				   return () 
	fun 1 n 

SPOJ 8670. THE MAX LINES is easy one. From problem’s figure you can see BC^2 = AB^2 + AC^2 [ from the property of semi circle ] so we can also write 4r^2 = ( AB^2 + AC ) + AC^2 - AC . We got quadratic in AC . Our variable point is A so lets say AC = x then we have s = -x^2 + x + 4r^2 . Differentiating s with respect to x we have \frac{d}{dx} s= -2x+1 and \frac{d^2}{dx^2} s = -2 <0  . Clearly we have maximum at \frac{d}{dx} s . Equating it to zero we get x = \frac 1 2 .Putting this value in s = -x^2 + x + 4r^2 we have s = 4r^2 + \frac 1 4 . Here is one more analysis.
PS. Some times i get bizarre problem with sourcecode tag. It was not rendering the code in below so i had to put the code first and analysis second :P.

Advertisements

June 12, 2011 - Posted by | Programming | ,

2 Comments »

  1. thank you, This is very helpful.. 🙂

    Comment by leli | September 26, 2011 | Reply

  2. i try solving this with c++, but got wrong answer 😦

    Comment by eve | October 8, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: