Ayağınızı sındırın!#11752
Breakdans ilk dəfə Olimpiya Oyunlarında təqdim ediləcək. Və siz bunun bir parçası olacaqsınız! Yaxşı, daha dəqiq desək, siz münsiflər heyətinin bir hissəsi olacaqsınız... Daha doğrusu, sizin vəzifəniz münsiflər heyətinin oturacağı stolun yığılmasıdır. Bu da böyük bir uğurdur, təbrik edirik!
Əslində, stolüstü artıq hazırdır: o düzdür, sabit eni və sıxlığı var, forması isə p_1p_2 \ldots p_n ilə ifadə olunan, heç bir üç təpəsi bir düz xətt üzərində yerləşməyən (yəni hər hansı üç təpədən bir xətt keçmir) -bucaqlının daxili sahəsindən ibarətdir. Sizin eyni uzunluqda və çox kiçik enə malik üç ayağınız var. Sizin vəzifəniz bu ayaqları stolun müxtəlif təpələrinə elə yerləşdirməkdir ki, stol sabit qalsın. Başqa sözlə, siz p_i, p_j və p_k təpələrini elə seçməlisiniz ki, bu p_ip_jp_k üçbucağının daxilində -bucaqlının ağırlıq mərkəzi yerləşsin (və bu üçbucağın sərhədlərində olmasın).
Bu işi neçə fərqli üsulla həyata keçirmək olar? Əgər iki üsul yalnız ayaqların yerlərinin dəyişdirilməsi ilə fərqlənirsə, onlar fərqli sayılmır.
Birinci sətirdə n~(3 \le n \le 10^5) ədədi verilir. Sonra sətir gəlir: bu sətirlərin -ci hər biri p_i təpəsinin koordinatları olan iki tam ədəd x_i və y_i~(-10^6 \le x_i, y_i \le 10^6) verir.
Qəbul edilir ki, hər hansı 1 \le i < j < k \le n üçün p_i, p_j və p_k təpələri bir düz xətt üzərində yerləşmir, həmçinin p_1p_2 \ldots p_n çoxbucaqlısı öz-özünü kəsmir.
Bir tam ədəd çıxarın — stolun sabit qalması üçün ayaqları yerləşdirməyin mümkün olan üsullarının sayını.
Nümunə 1
Nümunə 2
Nümunə 3