OFBEAT  Officers on the Beat
In the Middle Ages the capital of Byteland was surrounded by stout walls to protect the citizens from intruders. The gates of the city were well guarded and the drawbridge was lifted for the night, and everyone felt pretty happy and secure. At least, for a while.
With time the usual disadvantages of a walled city became apparent. As the population increased, crime flourished in the cramped living space. Eventually it all became so bad that the mayor decided to intervene. Some of the guards were reassigned from their usual occupation of reading newspapers in the guard posts near the gates, and told to start patrolling the city. Many of the officers were rather unhappy about all this, especially after the first men to go on the beat returned with bleeding noses and bumps on their heads. Sensing the low morale of the men, the Captain of the Guard, a bright young individual, decided to reinterpret the order he had received from the mayor. He decided that patrol officers would only go out in large groups and armed to the teeth, and would only move along a few carefully chosen streets from which they could see everything that was going on in the city without actually getting involved.
The city is laid out on a regular grid, with each street running NorthSouth or EastWest from one end of the city to the other (as far as the walls allow). Every point with integer coordinates is at an intersection of two streets, one leading NorthSouth, the other EastWest. The walls that surround the city form a simple polygon whose sides run directly alongside sections of some streets of the city.
Every street in the set of 'patrolled streets' chosen by the Captain intersects with at least one other patrolled street. Furthermore, if a point belongs to one of the streets of the city then it is visible from some point of one of the patrolled street (points see each other iff the line segment connecting them is a fragment of a street). Finally, the set of patrolled streets chosen by the Captain consists of the minimum possible number of streets.
Given a description of the capital of Byteland, find out how many of its streets were actually patrolled by guards after the Captain issued his order.
Input
The first line of input contains t  the number of test cases. t test cases follow.
For each test case, the first line contains a single integer n  the number of sections the city wall consists of (4 <= n <= 2000). The second line contains exactly n integers a_{1},...,a_{n} describing successive sections of wall (1<=a_{i}<=100000). Any two successive sections of wall are perpendicular to each other. The length of the ith section is the absolute value of a_{i}, while its direction is described by the sign of a_{i} (positive means northbound or eastbound, negative  southbound or westbound when traversing the walls clockwise).
Output
For each test case output a single integer k  the number of elements of the patrolled set of streets selected by the Captain.
Example
Input: 1 14 +2 +2 +2 +2 4 +2 +1 +2 3 +2 2 8 +4 2 Output: 4
hide comments
akshay tankha:
20120229 06:16:38
can anybody pls tell how the min no of streets is being calculated

Added by:  adrian 
Date:  20050205 
Time limit:  2.125s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  DASM Programming League 2004, problemset 6 