541

Эх өгүүлбэр

Энэ болдлогын гол санаа нь ямар нэгэн хоёр цэгийг бэхлээд тухайн цэгүүдээр зэргэлдээ оройгоо хийсэн квадрат олдох эсэхийг хайхаад хангалттай. Хайхдаа цэгүүдийн олонлгоо эрэмбэлээд хоёртын хайлт хийж болно. Мөн Hash хайлтын арга хэрэглэж болно. Хайлт хийхдээ P=20001*x+y гэж цэгээ бүхэл тоо болгон хувиргавал цэгээ эрэмбэлэх, Hash хайлт хийхэд илүү хялбар болно. Учир нь |x|<20001, |y|<20001 байгаа. Хэрэв code -оо C++ хэл дээр бичиж байгаа бол map өгөгдлийн бүтцийг ашигласан ч болох юм. Харин
A=(x[i]-y[j]+y[i], y[i]+x[j]-x[i]);
B=(x[j]-y[j]+y[i], y[j]+x[j]-x[i]);
Энд A, B цэгүүд нь (x[i], y[i]), (x[j], y[j]) цэгүүдтэй нийлэн квадрат үүсгэх боломжтой гэдэгийг хялбар тооцоолон олох боломжтой. Одоо A, B цэгүүд өгөгдсөн цэгүүдийн олонлогт зэрэг оршийх эсэхийг шалгахад л хангалттай. Энэ бодолт O(n^2log(n)) хугацаанд хэрэгжинэ.