CareerCup

[4,3,5,2,1,6,8,9,6,5...]. since all the movements are along x axis and y axis the convex Hull will have the longer edges parallel to the x axis or y axis so the minimum area rectangle will be having length and width parallel to x and y axis.. you need to know the maximum displacement along the each axis.. by dividing the sequence into two sequences (even and odd) for each axis [4,5,1...] [3,2,6...] taking the direction aspect a = [4,-5,1...] b = [3,-2,6...] take span(a) and span(b) where span(a) = maximum - minimum (coordinate on x axis that were reached) where span(b) = maximum - minimum (coordinate on y axis that were reached) multiple and thats your area.. {{{ #include <iostream> #include <cstring> using namespace std; int main() { int move[10]={4,3,5,2,1,6,8,9,6,5}; int max=0,min=0,cur = 0; for(int i =0;i<10;i+=2) { if(i%4 == 0) cur = cur + move[i]; else cur = cur - move[i]; if(cur>max) max = cur; if(cur<min) min = cur; } int len1 = max -min; max = 0; min = 0; cur = 0; for(int i =1;i<10;i+=2) { if((i-1)%4 == 0) cur = cur + move[i]; else cur = cur - move[i]; if(cur>max) max = cur; if(cur<min) min = cur; } cout<<"area is : "<<len1*(max-min)<<endl; return 0; } }} - kkr.ashish February 20, 2013 | Flag Reply

Actually it starts with 0,0,0,0 in the beginning and keep updating edge locations

- fw454@nyu.edu February 20, 2013 | Flag Reply

Here is a Python solution.

def compute_spiral_area(movements):
    i = 0
    max_x = 0
    min_x = 0
    max_y = 0
    min_y = 0
    x = 0
    y = 0
    while True:
        if i >= len(movements): break
        x += movements[i]
        if x > max_x: max_x = x
        i += 1
        if i >= len(movements): break
        y += movements[i]
        if y > max_y: max_y = y
        i += 1
        if i >= len(movements): break
        x -= movements[i]
        if x < min_x: min_x = x
        i += 1
        if i >= len(movements): break
        y -= movements[i]
        if y < min_y: min_y = y
        i += 1
    return (max_x - min_x) * (max_y - min_y)

input = [4,3,5,4,10]
print compute_spiral_area(input)

- showell30@yahoo.com February 21, 2013 | Flag Reply

My solution:

1. Arrive at a rectangle with lowest, highest of x, y with each movement : O(n)

2. Compute area of rectangle

3. Double the area -we will get the area of the triangle that can enclose.

- prasadbgv July 08, 2018 | Flag Reply

2 square units

- Sumit Gera February 20, 2013 | Flag Reply

35 sq units for the sample.

Find the min y and max y
Find min x and max x

Rectangle will be composed of two diagonally apposite points (min x, min y) and <max x, max y).

Length =max x - min x
Height = max y - min y

with the given sample...it is
Length=4 - (-1) = 5
Height=7-0=7 (assume x,y initial position as 0,0)
35=7*5

- SimpleOne February 23, 2013 | Flag Reply