TopCoder

unknown
我比tourist還要強!!!

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

75.0% (12/16)

Tags

Description

在計算幾何中,座標是十分常出現在題目中的元素,舉凡計算長度,角度,位置,距離等。而要描述座標,最簡單容易的就是描述該座標的每個分量。

而有了座標,便能清楚的描述多邊形在幾何平面或空間中的長相,或是某個點在平面上的位置。

當你學會用座標表示點後,你便開始記錄你時時刻刻在平面上的位置。由於你移動的時候都是走直線的,因此,你所記錄的座標兩兩間都是以直線到達,比如說上一個記錄的座標點爲 $(0,0)$,這次所記錄的座標點爲 $(1,1)$,你便是從座標 $(0,0)$ 走 $x=y$ 這條直線到達 $(1,1)$。

回家之後,你發現今天一共記錄了 $N$ 個座標點,你很好奇,究竟今天你左轉了幾次、右轉了幾次、回頭了幾次?

假設你現在行進的方向是朝着 $x$ 軸正方向前進,如果接下來往 $x$ 軸負方向前進便定義爲回頭,如果接下來往上半平面前進便定義爲左轉,如果接下來往下半平面前進便定義爲右轉。

Input Format

第一行包含一個整數 $N$,表示你記錄的 $N$ 個座標點。

接着包含 $N$ 行,每行包含兩個整數 $x_i,y_i$ 表示第 $i$ 個座標點的 $x$ 座標及 $y$ 座標。

  • $1 \le N \leq 10^ 6$
  • $0 \le |x_i|,|y_i| \le 10^ 9$
  • 保證所有相鄰的兩個座標點皆不相同

Output Format

輸出三個非負整數,分別代表左轉、右轉、回頭了幾次。

Sample Input 1

5
0 0
0 1
1 1
1 2
1 0

Sample Output 1

1 1 1

Hints

Problem Source

NEOJ Problem 400

Subtasks

No. Testdata Range Constraints Score
1 0~3 20
2 4~9 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2