Finále

D: Senzory

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Na obvodu jednotkového kruhu je umístěno N senzorů. Senzory mají zorný úhel α ≥ 90º (stejný pro všechny senzory), který určuje, jak velkou výseč prostoru jsou schopné vidět. Senzory spolupracují ve trojicích, ale komunikovat spolu můžou jenom tehdy, pokud na sebe všechny navzájem vidí. Vybereme nějaké tři senzory a zajímalo by nás, jakou máme šanci, že spolu nebudou schopny komunikovat (ani poté, co je vhodně natočíme). Chtěli bychom tedy spočítat, kolik existuje různých trojúhelníků ze zadaných senzorů takových, že spolu nemůžou komunikovat. Jinými slovy hledáme trojúhelníky, které mají jeden úhel o velikosti alespoň α. Trojúhelníky nesmí být degenerované, tedy všechny jejich úhly musí být ostře větší než 0º a ostře menší než 180º. Dva trojúhelníky jsou různé, pokud mají alespoň jeden různý vrchol.

Tvar vstupu

Na prvním řádku je číslo T udávající počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku dvě čísla: číslo N – počet senzorů na obvodu kruhu, a celé číslo α – úhel zadaný v miliontinách stupně. Máte zaručeno, že 90 000 000 ≤ α ≤ 180 000 000.

Na následujícím řádku je popis bodů zadaný jako N mezerou oddělených celých čísel. V pořadí i-té z nich je ci, úhlové souřadnice i-tého senzoru v miliontinách stupně, přičemž platí 0 ≤ ci < 360 000 000. Všechna ci jsou různá.

Tvar výstupu

Pro každý test vypište na samostatný řádek jediné číslo: počet různých nedegenerovaných trojúhelníků, které mají jeden úhel o velikosti alespoň α. Pozor, počet trojúhelníků může být velký a výsledek se tak nemusí vejít do běžně používaných datových typů jako je int v C/C++.

Lehká verze

  • T ≤ 10
  • 1 ≤ N ≤ 20 000
  • 0 ≤ ci < 360 000 000

Těžká verze

  • T ≤ 10
  • 1 ≤ N ≤ 10⁶
  • 0 ≤ ci < 360 000 000

Ukázkový vstup

3
4 90000000
0 180000000 1000000 359000000
8 110000000
0 45000000 90000000 135000000 180000000 225000000 270000000 315000000
2 90000000
0 200000000

Ukázkový výstup

3
24
0

Vysvětlení ukázkového vstupu a výstupu

V prvním testu jsou body umístěny postupně na 0º, 180º, 1º a 359º, označme je popořadě A, B, C a D. Velikost α je 90º. Snadno si všimneme, že trojúhelníky mající jeden úhel větší než α jsou přesně tři: ABC a ABD jsou dle Thaletovy věty pravoúhlé a kromě nich vyhovuje ještě trojúhelník ACD (jehož úhel u vrcholu A je jistě tupý).

Ve druhém testu je do kruhu vepsaný pravidelný osmistěn, α = 110º. Vyhovujících trojúhelníků je 24, z toho právě tři mají největší úhel u vrcholu na 0º.

Ve třetím testu nejsou žádné trojúhelníky.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)