시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 187 | 88 | 74 | 54.015% |
At the Colby’s Costly Collectibles workshop, special jewels are manufactured. In his production process Colby first creates a large grid of stones, each of which has the shape of an equilateral triangle. From this grid he cuts out all kinds of shapes which he sells as pieces of jewellery. Customers can choose their preferred shape according to the following basic rules:
To illustrate the production process, a typical jewel is depicted in the figure on the right. This corresponds with the third test case in the samples below.
Since the customer has to pay per triangle, Colby has asked you to help him calculate the number of triangles used. You are given a description of the jewel’s outer boundary. Note that it follows from rules 2 and 3 that the boundary will never intersect or touch itself.
The input starts with a line containing an integer T, the number of test cases. Then for each test case:
The boundary will never touch itself. It will always end up where it started and the total length of the boundary will not exceed 1000. The path starts at a vertex and the endpoint of every segment will again be a vertex. (In other words, no two consecutive edges in the input will be in the same direction, not even the first and the last edge.)
For each test case, output one line with a single integer N, the number of triangles.
3 3 x 1 z 1 y -1 3 y 333 x -333 z -333 23 y -3 z 2 y -2 x 1 y -1 z -1 x 1 y -1 x -1 z -1 x 2 z 1 x 1 y 1 z -1 x 1 z 2 x 1 z 2 x 1 z 1 x -1 z 1
1 110889 42
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2015 Preliminaries C번