COCI 2016/2017 - Contest 7 - Paralelogrami

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 7
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Gần đây, một trò chơi máy tính mới đã trở nên nổi tiếng, gọi là Parallelograms. Lúc bắt đầu trò chơi, máy tính sẽ vẽ ~N~ điểm lên màn hình với tọa độ là các số nguyên trong khoảng ~-10~ đến ~10~.

Nước đi duy nhất có thể được thực hiện là lấy ~3~ điểm không thẳng hàng ~A, B, C~ và thay thế điểm ~C~ bằng điểm ~D~ sao cho ~ACBD~ là một hình bình hành với một đường chéo là đoạn thẳng ~AB~. Dễ thấy điểm ~D~ luôn luôn tồn tại và là duy nhất.
Vào thời điểm bắt đầu trò chơi, tọa độ các điểm phân biệt đôi một, nhưng trong quá trình trò chơi diễn ra, nhiều hơn một điểm được phép có vị trí như nhau. Hơn nữa, tọa độ của mỗi điểm mới được tạo ra phải có giá trị tuyệt đối tối đa là ~10^9~.

Mục tiêu của trò chơi chính là sử dụng một chuỗi nước đi để đưa tất cả các điểm đến góc phần tư thứ nhất trong trục tọa độ. Nói cách khác hơn, khi trò chơi kết thúc, tất cả các điểm phải có tọa độ không âm.
Hãy tìm một chuỗi nước đi, gồm tối đa ~2\,500~ nước đi, mà sẽ đưa tất cả các điểm về góc phần tư thứ nhất, hoặc xác định chuỗi nước đi này không tồn tại.

Parallelogram: Hình bình hành

Input

Dòng đầu tiên chứa một số nguyên ~N\,(3 \le N \le 400)~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa tọa độ ~X_i, Y_i\,(-10 \le X_i, Y_i \le 10)~ của điểm thứ ~i~.

Vào thời điểm bắt đầu trò chơi, không có hai điểm nào có cùng tọa độ.

Output

Nếu chuỗi đáp án không tồn tại, in ra duy nhất một dòng chứa số ~-1~.

Nếu chuỗi đáp án tồn tại, trên dòng đầu tiên in ra số nguyên ~M\,(0 \le M \le 2\,500)~.
~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên phân biệt ~A, B, C\,(1 \le A, B, C \le N)~ là số thứ tự của các điểm được sử dụng trong nước đi đó. Tọa độ của điểm thứ ~C~ sẽ thay đổi như luật trên, và tọa độ của điểm thứ ~A~ và ~B~ sẽ không thay đổi.

Sample 1

Input
3
0 0
4 0
3 -1
Output
1
1 2 3

Sample 2

Input
4
5 0
0 5
-2 -2
-3 2
Output
2
1 2 3
1 2 4

Sample 3

Input
3
-1 -1
-2 -2
-3 -3
Output
-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.