40. Lacy 的彩色三角形

0 Judge

Code: 0


Lacy 的彩色三角形

題目敘述

Lacy 又想到一個好玩的石頭遊戲, Lacy 找了一些石頭, 一個一個隨便的丟在座標平面的整數點上, 然後玩奇怪的遊戲。但他發現, 如果石頭的凸包包住了原點, 或是原點剛好在凸包的邊界上, 就會被長老罵。 因為 Lacy 的記憶力不太好一次不能記太多的個石頭的座標, 但又想知道會不會被長老罵。如果你是 Lacy 有沒有辦法知道會不會被罵?

輸入說明

輸入的第一行包含一個整數 $T(T\leq 40)$,代表接下來有 $T$ 個 Lacy。接下來每個 Lacy 有 $N+1(N\leq 100000)$行,每個 Lacy 的第1行是 N 表示 Lacy 要丟 N 顆石頭, 接下來 $N$ 行表示每石頭放的座標 $(x,y)$ $(-10^6 \leq x,y \leq 10^6)$

為了模擬 Lacy 的記憶力, 這題的記憶體只有 0.4 MB

輸出說明

對於每個 Lacy,輸出一行,表示放下第幾個石頭後會背長老罵, 如過全部丟完都不會被罵輸出 "OWO"。

範例輸入

範例輸出

子題一[40%]

$ N \leq 100 $

子題三[60%]

無額外限制


Judge Setting

run-time limit: 5000 ms
memory limit: 424288 byte
測資數量: 3