AR
RU
EN
ES
ZH
FR
DE
PT
HI
إعادة بناء مضلع محدب من مجموعة مسافات
Python
Hard
math
مهمة «إعادة بناء مضلع محدب من مجموعة مسافات»
يوجد مجموعة من N نقطة على المستوى، تشكل مضلعًا محدبًا بترتيب المسح. جميع المسافات الزوجية بين الرؤوس معروفة، لكن ترتيب النقاط غير معروف. يجب استعادة الترتيب الأصلي للرؤوس (أرقامها من 1 إلى N) بحيث يكون المضلع الناتج محدبًا وله نفس المسافات الزوجية. من المضمون أن الحل فريد. اطبع أرقام الرؤوس بترتيب المسح في اتجاه عقارب الساعة، بدءًا من الرأس ذي الرقم الأصغر.
تنسيق الإدخال
السطر الأول يحتوي على عدد صحيح N (3 ≤ N ≤ 100). الأسطر N التالية تحتوي على N أعداد صحيحة لكل منها — مصفوفة المسافات A، حيث A[i][j] = A[j][i] هو مربع المسافة الإقليدية بين الرأس i والرأس j (0 ≤ A[i][j] ≤ 10^9). العناصر القطرية تساوي 0. المصفوفة متماثلة.
تنسيق الإخراج
أخرج N أرقامًا — أرقام الرؤوس بترتيب الاجتياز في اتجاه عقارب الساعة، بدءًا من أصغر رقم. إذا كان من المستحيل استعادة المضلع، أخرج -1.
أمثلة
مثال 1
الإدخال
4
0 1 4 1
1 0 1 4
4 1 0 1
1 4 1 0
الإخراج
1 2 3 4
مثال 2
الإدخال
5
0 2 5 5 2
2 0 2 5 5
5 2 0 2 5
5 5 2 0 2
2 5 5 2 0
الإخراج
1 2 3 4 5
مثال 3
الإدخال
5
1 2 3 4 5
5
3 4 5 6 7
الإخراج
main.py