Zadanie

KSP má tri písmena. P je \(16\). písmeno, S je \(19\). a K je \(11\). Keď odstránime dve jednotky z čísel \(16\) a \(19\) dostaneme \(6\) a \(9\). Koľko je \(9\)? To je \(3 \cdot 3\). Opakujem! Tri krát tri! TRI krát TRI. Koľko je \(6\)? To je \(3 + 3\). TRI + TRI! Náhoda? Myslím, že nie! Trojsten confirmed.

Niektoré veci proste nie sú náhodné. Čo sa stane, keď spojíte všetky “é” na tejto strane? Dostanete trojuholníky. Všetky trojuholníky! Každé Tri “é” tvoria trojuholník. To nie je náhoda! Trojuholníky nie sú náhoda. Prečo? Koľko majú strán? TRI! Keď veci tvoria veľa trojuholníkov, to nie je náhoda!

Úloha

Máte zadané body v rovine. Zistite, ako veľmi nenáhodné sú, teda vrcholy koľkých trojuholníkov tvoria.

Formát vstupu

Na prvom riadku vstupu je počet rôznych bodov \(n\) (\(0\leq n\leq 4\,000\)).

Nasleduje \(n\) riadkov a na každom sú dve celé čísla \(x_i\), \(y_i\) (\(-100\,000 \leq x_i, y_i \leq 100\,000\)), ktoré sú súradnicami daného bodu.

Formát výstupu

Vypíšte počet trojuholníkov s vrcholmi v daných bodoch.

Príklady

Input:

5
4 5
21 22
5 6
0 1
-5 -4

Output:

0

Tieto body sú jednoznačne náhodné.

Input:

5
0 0
3 3
3 0
0 3
1 -1

Output:

10

Toto naozaj nemôže byť náhoda.

Najhrubšia sila

Najprv si potrebujeme uvedomiť, kedy tri body tvoria trojuholník. Vždy, keď nie sú na jednej priamke. Ako sa to dá otestovať? Môžeme si vyjadriť rovnice všetkých strán potenciálneho trujuholníka a porovnať ich. Nejde to aj ľahšie? Samozrejme, že ide. Stačí nám totiž vyrátať len smernice daných úsečiek (tangens uhlu, ktorý zvierajú s osou \(x\)) a ak sú rovnaké, tak sú dané úsečky rovnobežné a teda nemôžu tvoriť trojuholník. Ale ide to ešte ľahšie.

Môžme si uvedomiť, že trojuholník je len na jednej priamke (teda to nie je trojuholník) práve vtedy, keď má nulový obsah. Najjednoduchší a najlepší spôsob, ako zistiť, či tri body \(A,B,C\) ležia na jednej priamke, je spočítať vektorov \((C-A)\) a \((B-A)\) a overiť či je nulový. V dvoch rozmeroch vypočítame vektorový súčin \(v\times u = vx \cdot uy - ux \cdot vy\), kde napr. \(vx\) je \(x\)-ová zložka vektora \(v\).

Výhody vektorového súčinu:

  • Je rýchly a jednoduchý.
  • Pokiaľ body mali celočíselné súradnice, tak vektorový súčin môžeme spočítať v celých číslach, čím sa vyhneme nepresnostiam.
  • Funguje aj pre všelijaké patologické prípady, kedy je viac bodov na rovnakom mieste a podobne.

No a už máme prvé riešenie. Prejdeme všetky trojice bodov (dávame si ale pozor na opakovania) a pre každú trojicu si zistíme, či tvorí korektný trojuholník. Dostávame riešenie v čase \(O(n^3)\).

#include<cstdio>
#define For(i, n) for(int i = 0; i<(n); ++i)
typedef long long ll;
int n, X[4007], Y[4007];

int main() {
    scanf("%d",&n);
    For(i, n) scanf("%d%d", X+i, Y+i);
    int pocet = 0;
    For(i, n) For(j, i) For(k, j) {
        ll x1 = X[i]-X[j], y1 = Y[i]-Y[j];
        ll x2 = X[i]-X[k], y2 = Y[i]-Y[k];
        // vektorový súčin
        if (x1*y2 - x2*y1 != 0) pocet++;
    }
    printf("%d\n",pocet);
}

O hľadaní v priamkách

Dôležitá myšlienka na ceste k lepšiemu riešeniu je, že to môžeme počítať aj naopak. Keby každá trojica bodov tvorila trojuholník, tak by sme mali \(\frac{n(n-1)(n-2)}{6}\) trojuholníkov. Potom, ak by sme vedeli zrátať počet trojíc, ktoré netvoria trojuholníky, tak ich len odrátame a máme riešenie. Budeme teda rátať trojice bodov, ktoré netvoria trojuholník, resp. ktoré ležia na jedne priamke. Od teraz uvažujme len priamky, na ktorých sú aspoň 2 body z našej množiny. Potom maximálny počet rôznych priamok je \(\frac{n(n-1)}{2}\), čo nie je až tak veľa.

V podstate by sme chceli pre každú priamku zistiť, koľko bodov na nej leží. Ale potrebujeme to spraviť rýchlo. Napríklad to môžeme spočítať tak, že najprv preskúmame priamky, ktoré prechádzajú prvým bodom, potom priamky, ktoré prechádzajú druhým, atď.

Ku každému bodu si vieme vyrátať smernice (uhol, aký zviera s osou \(x\)) všetkých priamok, ktoré ním prechádzajú. Prejdeme teda všetky ostatné body, vyrátame smernicu a uložíme si ju. Takýchto smerníc potom budeme mať \(n-1\). Niektoré smernice budú rôzne, ale budú tam nejaké zhluky rovnakých smerníc.

Čo ale znamená, že pre dva body nám vyjde rovnaká smernica? No to, že sú spolu s pôvodným bodom na tej istej priamke a teda netvoria trojuholník. Ak nám pre \(m\) bodov vyjde tá istá smernica, tak aj s pôvodným máme \(m+1\) bodov, ktoré ležia na jednej priamke a netvoria trojuholníky. Dokopy to je \(\frac{m(m-1)}{2}\) trojíc, ktoré netvoria trojuholníky a je v nich pôvodný bod. Na to, aby sme vedeli zistiť, koľkokrát sme dostali ktorú smernicu si ich môžeme jednoducho usporiadať a prejsť. (Prípadne sa dajú pamätať v tzv. mape.) Oba postupy nás stoja čas \(O(n \log(n))\).

Nakoľko tento postup musíme urobiť pre každý bod, dostávame riešenie s časovou zložitosťou \(O(n^2 \log(n))\). Pamätať si musíme len pôvodné body a pre jeden aj všetky smernice. Pamäťová zložitosť je teda \(O(n)\). Pri celom tomto postupe si ale treba dávať pozor na to, že každú trojicu, ktorá netvorí trojuholník zarátame trikrát. Druhá nepríjemnosť je, že smernice nie sú celé čísla. Tu pomôže, že smernica je len podiel dvoch celých čísel (lebo súradnice trojuholníkov sú celočíselné) a takéto racionálne číslo si vieme pamätať ako dvojicu (pair<> v C++). Tieto zlomky však treba previesť do základného tvaru, teda vydeliť najväčším spoločným deliteľom (funkcia __gcd() v C++).

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#define For(Q,W) for(long long Q=0; Q<W; Q++)
using namespace std;
typedef long long L;

bool cmp(pair<L,L> a,pair<L,L> b){
    return a.second*b.first < b.second*a.first;
}

int main() {
    long long n;
    scanf(" %lld ",&n);
    vector<pair<L,L> > body;
    For(i,n){
      L a, b;
      scanf(" %lld %lld ",&a,&b);
      body.push_back(make_pair(a,b));
    }
    L vsetkych = (n*(n-1)*(n-2))/6;
    L zlych =0 ;
    For(i,n){
      vector<pair<L,L> > priamky;
      pair<L,L> a = body[i];
      
      For(j,n){
        if(i==j) continue;
        pair<L,L> b = body[j];
        pair<L,L> c = make_pair(b.first - a.first, b.second - a.second);
        if( c.first < 0) {
          c.first = 0ll-c.first;
          c.second = 0ll-c.second;
        }
        else{
          if (c.first ==0) c.second = abs(c.second);
      }
      
        priamky.push_back(c);
      }
      
      sort(priamky.begin(), priamky.end(),cmp);
      
      if(priamky.size()>0){
        pair<L,L> smernica= priamky[0];
        L pocet_na_nej=1;
        for(L j=1;j<priamky.size();j++){
          if(priamky[j].first*smernica.second == priamky[j].second*smernica.first){
              pocet_na_nej+=1;
          }
          else{
              zlych += (pocet_na_nej*(pocet_na_nej-1))/2;
              pocet_na_nej =1;
              smernica=priamky[j];
          }
        }
        zlych += (pocet_na_nej*(pocet_na_nej-1))/2;
      }
      
    }
    printf("%lld\n",vsetkych-zlych/3);
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.