Bucaqlı nöqtəli dördbucaqlıların sayı#1710
Aşağıdakı 10 \times 10 şəbəkədə beş fərqli bucaqlı nöqtəli dördbucaqlı görə bilərsiniz. (Bucaqlı nöqtəli dördbucaqlı o dördbucaqlıdır ki, onun bütün təpələri tam ədədi koordinatlara malikdir, tərəflər yalnız təpələrdə kəsişir və heç bir daxili bucaq dərəcəyə bərabər deyil.) Əlbəttə, bunlar 10 \times 10 şəbəkəsində çəkilə bilən milyonlarla bucaqlı nöqtəli dördbucaqlının yalnız bir neçəsidir. N \times N ölçülü şəbəkə verildikdə, bu şəbəkədə qurula bilən fərqli bucaqlı nöqtəli dördbucaqlıların sayını müəyyənləşdirməlisiniz.
Girişdə ən çoxu test var. Hər sətirdə bir tam ədəd (0 < N < 121) verilir. Giriş sıfır olan bir sətrə çatır.
Girişin hər sətri üçün çıxışda ayrıca sətirdə cavab verin. Hər bir çıxış sətrində iki tam ədəd olmalıdır: girişdəki -in dəyəri və N \times N şəbəkə üçün bucaqlı nöqtəli dördbucaqlıların sayı. Zəmanət verilir ki, cavab -bitlik işarəli tam ədədə yerləşəcək.
Xəbərdarlıq: Bu məsələnin müəllif həllindən başqa alternativ həlli yoxdur. Test nümunələrini yoxlamaq üçün kobud güclü həll yaza bilərsiniz. Beləliklə, proqramı təxminən saat işlədərək kiçik şəbəkələr üçün (dəqiq desək 22 \times 22-yə kimi) bütün cavabları tapa bilərsiniz.
İpucu: Bu məsələnin zaman limiti saniyədir. Səmərəli həll tapmaqda çətinlik çəkirsinizsə, əvvəlcədən hesablama daha yaxşı yol ola bilər. Hər halda, kobud güclü metod GHz Pentium IV kompüterdə təxminən il vaxt aparar.
Nümunə 1