TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

91.7% (22/24)

Submission's AC Ratio

28.1% (38/135)

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 1

3
0 1
2 3
4 5

Sample Output 1

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

No. Testdata Range Score
1 0 11
2 1 11
3 2 11
4 3 11
5 4 11
6 5 11
7 6 11
8 7 11
9 8 12

Testdata and Limits

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