Delaunay üçbucaqlanması

Müstəvidə verilmiş nöqtələr dəstinin üçbucaqlar dəsti, aşağıdakı şərtləri təmin edirsə, triangulyasiya adlanır:

1. Üçbucaqların zirvələri yalnız verilmiş dəstin nöqtələridir və dəstin hər bir nöqtəsi ən azı bir üçbucağın zirvəsi olmalıdır.

2. İki fərqli üçbucaq ya ümumi nöqtəyə malik deyil, ya ümumi zirvəyə malikdir, ya da ümumi tərəfə malikdir (lakin onların kəsişmə sahəsi həmişə 0-a bərabərdir).

3. Verilmiş nöqtələr dəstinin konveks qabığı daxilində yerləşən istənilən nöqtə ən azı bir üçbucağa aid olmalıdır (əgər o, onların ümumi zirvəsi və ya ümumi tərəfinə aid olarsa, bir neçə üçbucağa aid ola bilər). (Bəzi nöqtələr dəstinin konveks qabığı, bütün bu nöqtələri əhatə edən ən kiçik konveks çoxbucağa deyilir).

Triangulyasiya Delone triangulyasiyası adlanır, əgər əlavə olaraq, aşağıdakı şərt yerinə yetirilirsə:

• Triangulyasiyadakı istənilən üçbucaq ətrafında təsvir olunan dairənin daxilində heç bir verilmiş nöqtə yerləşmir (nöqtələr dairənin üzərində yerləşə bilər, xüsusən də, aydın olduğu kimi, nəzərdən keçirilən üçbucağın zirvələri dairənin üzərində yerləşir).

Verilmiş nöqtələr dəsti üçün onun Delone triangulyasiyalarının sayını tapın (iki triangulyasiya fərqli hesab olunur, əgər onlar ən azı bir üçbucaqla fərqlənirsə).

Giriş verilənləri

Giriş faylının ilk sətirində N – verilmiş dəstin nöqtələrinin sayı (3 ≤ N ≤ 30) yerləşir. Növbəti N sətir hər biri bir cüt həqiqi ədəd – müvafiq nöqtənin koordinatlarını ehtiva edir. Heç bir üç nöqtə eyni düz xətt üzərində yerləşmir.

Çıxış verilənləri

Çıxış faylına verilmiş nöqtələr dəstinin fərqli Delone triangulyasiyalarının sayını yazın.

Nümunələr