切割線
現在在一個平面上放著一個直徑為 \( 10^{114514}\) 的圓形披薩,中心在 \( (0,0)\)
上面有一些 \( n\) 個配料,第 \( i\) 個在座標 \( (x_i,y_i)\)
現在有一把神金神奇的刀,可以沿著兩個配料的方向切一刀
!a002要用這把刀切兩次這個披薩切出四塊,然後使得切出來的四塊符合以下條件 (在披薩片邊界上的配料等於不存在)
- 其中兩塊上的配料至少有 \( \lfloor \frac{n-4}{2} \rfloor\) 個配料,且這兩塊不相鄰 (茂瓜要吃的)
- 另外兩塊上沒有配料 (給
神金神奇刀吃的)
但是連 a002 都寫不出來的他根本不知道怎麼切,所以需要你的幫助,告訴他怎麼切
可以證明必定有解
輸入格式
第一行有一個數字 \( n(6 \le n \le 2 \times 10^5)\),代表有幾個配料
接下來 \( n\) 行每行有兩個數字,第 \( i\) 行的數字代表第 \( i\) 個配料的座標 \( (x_i,y_i)(-10^9 \le x_i,y_i \le 10^9)\)
保證任三個配料不共線
輸出格式
輸出兩行,每行輸出兩個數字,分別代表要沿著哪兩個配料切
配料編號 \( 1 \sim n \),可以重複用同一個配料
一定要切出四塊,不能只有兩塊或三塊(不然刀刀吃不飽會生氣)
範例輸入
6
2 3
-1 2
4 2
2 1
-1 -1
1 -1
範例輸出
2 4
1 6
範例解釋
子題配分
編號 | 範圍 | 分數 | 前置條件 |
---|---|---|---|
1 | \( 6 \le n \le 10, -10 \le x_i,y_i \le 10 \) | 10 | 無 |
2 | \( 6 \le n \le 10^3, -10^3 \le x_i,y_i \le 10^3 \) | 30 | 子題 1 |
2 | \( 6 \le n \le 2 \times 10^5, -10^9 \le x_i,y_i \le 10^9 \) | 60 | 子題 1,2 |
Comments