Given a sequence of n points on a paper which are expressed by Cartesian coordinates. You have to start at any point (not necessarily from one of the n points), and draw polyline (contiguous segments of straight lines) that go
through all of the points, i.e. your pen must not leave the paper, and you must go through all n points with straight line only (no curve).
How many turns, at least, do you need to make?
Note that you have to connect the points "in order", that is, you must connect the n points one after another following the order in the given sequence. You may, however, traverse some points prior to connecting all points before it in the sequence, but going through it before going through all points before it does not count.
First line contains a number T, denoting the number of testcases.
Each test case start with one line containing an integer n, denoting the number of points. The next n lines will each contain two integers. The i-th line denoting the i-th points coordinator you have to go through with polyline.
T<=100
1<=n<=1000
All coordinators are in range [0,10000].
No different two points have the same position.
For each testcase you have to output a number in a line, denoting the least turn you need.
4 4 0 0 0 1 1 1 1 0 4 0 0 1 1 2 1 3 0 4 0 0 1 0 2 0 3 0 4 0 0 0 3 0 1 0 2
2 1 0 2
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|