切割線


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

現在在一個平面上放著一個直徑為 \( 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

There are no comments at the moment.