Hi
Here is some code .. which does it in linear time in one pass .. you
cant do better than that since you need to read the directions atleast
once.
int area( ){
int ret = 0 , x=0;
while (// there are more chars ) {
//read next char into ch
switch ( ch ){
case 'n': y++;
break;
case 's': y--;
break;
case 'e': area += y;
break;
case 'w': area -= y;
break;
};
}
return abs ( ret );
}
-Dhyanesh
On 11/21/05, pramod <[EMAIL PROTECTED]> wrote:
>
>
> Here's another interesting problem I came across:
>
> You are to compute the area of the polygon described a set of vertical
> and horizontal lines.
> · The input to your program describes a path around the polygon.
> · The path is described as a set of directions:
> o North: 'n'.
> o East: 'e'.
> o South: 's'.
> o West: 'w'.
> · The path description will be terminated by a period, '.'.
> · The path will never cross itself and will never go over the same
> area twice.
> · You may assume that the path is made up of no more than 50000
> segments.
>
> Here is some sample input:
> e n w s .
> n e s e n e s s w w w n .
> and the output corresponding to the input:
> 1
> 5
>
> How quickly can you compute the area of a polygon described in this
> fashion?
> What is the order of the computation that needs to be performed?
> How small a program can you write to perform this computation?
>
> -Pramod
>
>
