Finále

D: Senzory

Řešení (Zadání úlohy)

Na první pohled se může zdát, že k vyřešení úlohy je potřeba použít hromadu goniometrických funkcí a geometrických vzorečků. Ve skutečnosti nám stačí jedno jednoduché pozorování ze středoškolské geometrie: máme-li body AB na kružnici, pak ať zvolíme libovolný bod C na delší straně kružnice, je velikost úhlu ACB vždy stejná a navíc jde snadno spočítat jen ze znalosti bodů AB. Konkrétně označíme-li střed kružnice jako S, platí |∠ACB| = |∠ASB| / 2. Pokud C zvolíme na kratší straně, pak platí |∠ACB| = 180 º - |∠ASB| / 2. S podobným tvrzením jste se nejspíš setkali na hodině matematiky, jeho důkaz naleznete například na české Wikipedii.

Nyní už se můžeme vrhnout na řešení úlohy:

Lehká verze

Pomalé řešení, které sice nestačí ani na lehčí variantu, ale může sloužit například pro ověření správnosti rychlejšího algoritmu, je následující: vyzkoušíme všechny možné neuspořádané trojice bodů a pro každou ověříme, zda má trojúhelník nimy tvořený aspoň jeden úhel větší než α. To se provede snadno: pro každou dvojici úhlových souřadnic ci, cj platí, že velikost úhlu, kterou odpovídající body svírají se středem kružnice, spočteme jako |ci - cj|. Pomocí předchozího tvrzení pak stačí ověřit, zda je bod C na delší nebo kratší straně kružnice a podle toho spočítat velikost úhlu ACB. Navíc jelikož α ≥ 90 º, můžeme si snadno rozmyslet, že má smysl zkoušet jen tu dvojici bodů, ve které třetí bod leží mezi nimi na kratším oblouku, neboť jedině tam je úhel ≥ 90 º.

Toto řešení má časovou složitost O(n³), což na lehkou variantu nestačí. Není však těžké zrychlit ho na O(n²): stačí si všimnout, že pokud nějaké body A, B už svírají se středem dostatečně malý úhel (takže 180 º - |ASB| / 2 je velké), vyhovovat budou právě všechny trojúhelníky ABC, ve kterých za C vybereme nějaký bod na kratším oblouku mezi AB.

Provedeme tedy to, že vyzkoušíme všechny (neuspořádané) dvojice AB a pro každou ověříme, zda je úhel ASB dostatečně velký, a pokud ano, připočteme k výsledku počet bodů mezi AB na kratší straně kružnice. Tak každý trojúhelník započteme jednou za každý jeho úhel větší roven α, ale jelikož α ≥ 90º, bude mít každý trojúhelník nejvýš jeden takový úhel, takže každý hledaný trojúhelník započteme právě jednou.

Jak hned uvidíme, bude se nám hodit neuspořádané dvojice bodů procházet tak, že pro každé A projdeme všechna B, která mají větší úhlovou souřadnici. Ve všech trojúhelnících, které projdeme, tedy bude bod A mít nejnižší souřadnici, bod B nejvyšší a bod C bude uprostřed.

Těžká verze

Předchozí řešení jde ještě více zrychlit. Pozorujme, co se bude dít pro jedno konkrétní A, když k němu postupně vybíráme B napravo od něj. Nějakou dobu pro něj vyhovují všechny body C mezi AB, až do okamžiku, než se úhel ASB příliš zvětší a pak už nevyhovují žádná C mezi AB.

Pro každé A si tedy můžeme spočítat jeho Bmax, což bude nejpravější bod, pro který ještě trojúhelníky ABC započítáme. Počet vyhovujících trojúhelníků, které mají nejlevější bod v A, pak spočteme jako 1 + 2 + … + (N - 1) + N = N(N + 1) / 2, kde N je počet bodů mezi ABmax.

Jak nám toto pozorování pomůže? Můžeme si všimnout, že když se z bodu A posuneme o jedna doprava, i Bmax se nám posune doprava. Můžeme tedy postupně procházet všechny body A a pokaždé jen aktualizovat pozici pointeru ukazujícího na aktuální Bmax. Tak sice po jednom posunutí A můžeme provést hodně posunutí ukazatele na Bmax, ale dohromady s ním nanejvýš dvakrát objedeme celou kružnici, takže ho posuneme O(n)-krát. Nebýt tedy třízení v O(n log n), které musíme provést, abychom body mohli procházet od nejmenšího, byla by časová složitost lineární.

Kód (C++)

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

const int FULL = 360000000;
int read = 0;

void solve(void)
{
	int N, a;
	read = scanf("e;%d %d"e;, &N, &a);
	int p[2 * N];
	for (int i = 0; i < N; i++)
		read = scanf("e;%d"e;, &p[i]);

	int cmp(const void *p, const void *q) {
		return *(const int *)p - *(const int *)q;
	}

	qsort(p, N, sizeof(*p), cmp);

	for (int i = 0; i < N; i++)
		p[i + N] = p[i] + FULL;
		// Nakopírujeme si body cyklicky, aby se nám s nimi lépe pracovalo

	long long cn = 0;
	int j = 0;
	for (int i = 0; i < N; i++) {
		while (p[j] - p[i] < 2 * a) // Toto funguje díky tomu, že máme body dvakrát
			j++;
		int inside = N - (j - i + 1);
		cn += (long long)inside * (inside + 1) / 2;
	}

	printf("e;%lld\n"e;, cn);
}

int main(void)
{
	int T;
	read = scanf("e;%d"e;, &T);
	while (T--)
		solve();
}

Máš na to!

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