HI
RU
EN
ES
ZH
FR
DE
PT
AR
यहाँ आपका अनुवाद है: दूरियों के एक सेट से उत्तल बहुभुज का पुनर्निर्माण
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