TopCoder

Thumb 100
$SCJ$
$SCJ$

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

21.1% (16/76)

Tags

Description

到底要不要喝呢?瓶蓋開了(如果你這題AC了),妁艷卻猶豫了起來。

這時妁艷收到一封簡訊,是妹妹寄來的:「學校好暗,我好害怕。快來接我回家。」

「哼哼,我才不要呢~」,雖然嘴巴這麼說,妁艷還是立刻趕到了學校。

深夜的女校門口,讓妁艷感到一股說不上來的不對勁,他看了看四周:一如往常的街道,曾經試著爬過但永遠翻不過去的圍牆,校門對面那些專門坑學生錢的黑店,人來人往的熱鬧街道......。等等,路上好冷清啊,空蕩蕩的一個人也沒有。「也是呢,這麼晚了人來人往也是很恐怖。」妁艷做了幾個深呼吸穩定情緒,說服自己一切正常。

妁艷按下開門鈕,寂靜,甚麼事也沒發生。他轉向警衛室,警衛剛好不在。只好靠自己了。這時妁艷發現門的旁邊有一個鍵盤,上面有16個按鈕還有一個小螢幕。這是要輸入密碼吧,解鎖甚麼的我最會了。妁艷研究了起來。

密碼是這樣的:
螢幕上有N個格子點。以a.x、a.y分別表示一個點的x、y座標。如果兩個點a , b滿足(a.x - b.x)*cos(π*a.y)*cos(π*b.y) > 0,則稱這個點對是恐怖的。這N個點所組成的恐怖點對數就是密碼。(a,b)和(b,a)算同一組點對。

槓,點這麼多要怎麼算啊,妁艷開始失望的亂敲鍵盤。

快幫助妁艷在最短的時間內找出密碼吧。

Input Format

第一行有一個正整數N,代表有幾個格子點。接下來的N行,每行有兩個整數x,y,代表每個點的座標。

2 ≤ N ≤ 300,000
0 ≤ 座標的絕對值 ≤ 109,且點不會重疊。

Output Format

輸出一個整數,代表密碼。

Sample Input

3
0 1
2 3
4 5

Sample Output

3

Hints

  1. 當|n|是奇數時,cos(π*n) = -1,當|n|是偶數或0時,cos(π*n) = 1。

2.
(2-0)*(-1)*(-1) = 2 > 0
(4-0)*(-1)*(-1) = 4 > 0
(4-2)*(-1)*(-1) = 2 > 0

  1. 聽說輸入密碼的鍵盤長的像下面這樣

Problem Source

原TIOJ1753 / problem setter : esrever

Subtasks

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2300 65536 65536
1 2300 65536 65536
2 2300 65536 65536
3 2300 65536 65536
4 2300 65536 65536
5 2300 65536 65536
6 2300 65536 65536
7 2300 65536 65536
8 2300 65536 65536