###### tags: `xivlo`

# Zajęcia 22.03.2021

## "Zakochany żab"
Zadanie podobne do zadania "Autostrady", tylko że krawędzie musimy wyliczyć sami. Trzeba wyliczyć krawędź między każdym kamieniem - można to zrobić za pomocą wzoru na odległość między punktami:
$$
d(A,B) = \sqrt{ (B_x - A_x)^2 + (B_y - A_y)^2 }
$$
Zamiast zwracać sumę krawędzi w MST, szukamy maksimum.

## Błędy w zadaniu Autostrady
- złe odczytanie limitów w zadaniu

                   // powinno: (bo tyle miast)
int Rank[1000006]; // np 1006
int repr[1000006]; // np 1006

pair< int, pair< int, int> > krawedzie[1000006]; //bo tyle autostrad

- złe sortowanie tablicy krawędzi

pair< int, pair< int, int> > krawedzie[1000006];
...
for(int i=1; i<=e; i++){ //i=0 ; i<e
    cin>>a>>b>>w;
    krawedzie[i]=make_pair(w, make_pair(a,b));
}

sort(krawedzie, krawedzie+e);

// sortuje od 1 do e
//sort(krawedzie+1, krawedzie+e+1);

- "czy mam robić Union?"
w Unionie:

if(ra==rb){
    return; //dla void
}

- makeSet

makeSet(n);
cin>>n;

## Tablica