Δύσκολο πρόβλημα από το cmad

ioannidis007 · Τρί Δεκ 23, 2008 9:50 pm

Εύκολο μέρος:

Για Ν σημεία στο χώρο, με συντεταγμένες (xi,yi,zi) για 2<=i<=N<=10000, να βρείτε τη μέγιστη απόσταση manhattan μεταξύ δύo σημείων, καθώς και τα σημεία που απέχουν περισσότερο.

Δύσκολο μέρος:

Ο αλγόριθμός σας να τρέχει σε Ο(n).

Αρχείο Εισόδου:

input.in
N
x1 y1 z1
x2 y2 z2
.
.
.
xN yN zN

Αρχείο εξόδου(Έστω τα σημεία i,j απέχουν περισσότερο)

output.out
i
j
d(i,j)

Τρί Δεκ 23, 2008 11:18 pm

http://pastebin.com/m2b4d5ea

Μάλλον από τον κώδικα δεν θα καταλάβετε και πολλά. Δεν εξηγώ ακόμα την λύση μου

Μερικά hints:
1. Σκεφτείτε πρώτα το πρόβλημα σε 2 διαστάσεις... πώς θα μπορούσατε να βρείτε τα δύο σημεία που απέχουν περισσότερο;
2. Για d διαστάσεις, έχουμε 2^d περιπτώσεις...

userresu · Τετ Δεκ 24, 2008 1:35 am

Χμμ η μεγαλύτερη δυνατή απόσταση σε 2 διαστάσεις λογικά θα είναι max(dist(a,b),dist(c,d)), όπου a το σημείο με ελάχιστο άθροισμα συντεταγμένων, b το σημείο με μέγιστο άθροισμα συντεταγμένων, c το σημείο με ελάχιστη διαφορά συντεταγμένων και d το σημείο με μέγιστη διαφορά συντεταγμένων.

Αλλά μπορεί και όλο αυτό να είναι μία απέραντη κοτσάνα

EDIT: Επειδή μάλλον σωστό είναι, ας εξηγήσω τη σκέψη μου. Η απόσταση 2 σημείων a,b είναι ουσιαστικά |a.x-b.x|+|a.y-b.y|. Έχουμε 4 περιπτώσεις:
1) a.x>=b.x και a.y>=b.y => a.x-b.x+a.y-b.y
2) a.x>=b.x και a.y<b.y => a.x-b.x-a.y+b.y
3) a.x<b.x και a.y>=b.y => -a.x+b.x+a.y-b.y
4) a.x<b.x και a.y<b.y => -a.x+b.x-a.y+b.y

Κάπως έτσι βγαίνει.

EDIT 2: Για ν διαστάσεις, η απόσταση 2 σημείων είναι |a.d1-b.d1|+|a.d2-b.d2|+...+|a.dv-b.dv|, όπου d1,d2,...,dν είναι διαστάσεις. Άρα, αφού για κάθε όρο έχουμε 2 περιπτώσεις, θα έχουμε σύνολο 2^ν περιπτώσεις.