(Analysis by Dhruv Rohatgi and Brian Dean )

Intuitively, a clockwise fence will "tend" to turn right, and a counterclockwise fence will tend to turn left. More concretely, for every two adjacent fence segments, one can compute the angle turned at that corner: either no turn (if the two segments are in the same direction), or a turn by $90^{\circ}$ counterclockwise (e.g. if the first segment is E and the second is N), or a turn by $-90^{\circ}$ counterclockwise (e.g. if the first segment is E and the second is S). Doing a few examples by hand will reveal that the sum of these angles, over all corners of the fence, is precisely $360^{\circ}$ if the fence is counterclockwise, and $-360^{\circ}$ if clockwise (other sums can be achieved if the fence is allowed to intersect itself, but we don't have to worry about this complication in this problem).

This fact can be proven a variety of ways, such as by inducting on the area of the region enclosed by the fence. It gives a linear-time algorithm, shown below.

Dhruv's code:

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

int angle_from_direction(char a)
{
if(a == 'E') return 0;
if(a == 'N') return 90;
if(a == 'W') return 180;
if(a == 'S') return 270;
}

int angle_change(char a,char b)
{
int theta1 = angle_from_direction(a);
int theta2 = angle_from_direction(b);
if(theta2 == (theta1 + 90)%360) return 90;
else if(theta2 == theta1) return 0;
else if(theta2 == (theta1 + 270)%360) return -90;
else assert(false);	//fence should not backtrack on itself
}

void test(string s)
{
int total_change = 0;
for(int i=0;i<s.size();i++)
total_change += angle_change(s[i],s[(i+1)%s.size()]);
if(total_change == 360) cout << "CCW\n";
else cout << "CW\n";
}

int main()
{
int N;
string s;
cin >> N;
for(int i=0;i<N;i++)
{
cin >> s;
test(s);
}
}


There are several other ways to effectively approach this problem. For example, one can look at the direction of any "boundary" segment. That is, look any horizontally-oriented segment that is as far north as possible --- if it is directed east, the entire path must be clockwise, and if directed west, the entire path must be counterclockwise. In fact, we can draw any horizontal or vertical line through the scene and deduce from the direction of the segments along this cross section the overall orientation of the fence. For example, if we draw a horizontal line through the scene, it will be cut by some vertical segments pointing north and some pointing south (in fact, these will alternate in direction along the cross section); if the westmost segment points north, the entire path has a clockwise orientation, and vice versa.

The shoelace formula for computing areas of polygons also leads to a solution for this problem, since it delivers a "signed" area, being positive or negative depending on the orientation of the polygon in question.