1974 ACM-ICPC World Finals Problem

general
1

Given an array of String containing the dimensions to create a figure, we have to calculate the area of the figure created from the string array.

Example : If the string array contains {“N2” , “E2” , “S2” , “W2”}
N → North E->East and so on.
The above array represents a square with side 2.

Similarly any figure can be created with at most 12 corners and assume that we always end on the corner on which we started.
I used 2-D matrix to first create the figure using 1s and 0s and then calculated the area.

Is there any better approach to solving this problem as my program gives wrong answer for one case?
The exact question can be found here :
http://icpc.baylor.edu/ICPCWiki/attach/Problem%20Resources/1974-Texas.pdf

2

I think you can use simple geometry to solve the problem.

You can assume that you always start at coordinates (0, 0).
Each time when you move, you can update the coordinates and compute part of the result using Shoelace Formula.

Note that constant memory is sufficient to solve this problem.

3 Likes