Водопровод - 2 C++

На плане местности изображено N дачных домиков, которые имеют известные координаты X, Y (i=1..N)Какой минимальной длины должна быть суммарная длина труб водопровода, который соединит все N домов городка непосредственно или через несколько промежуточных домиков? 

Входные данные

   В первой строке число N - количество домиков. В следующих N строках координаты домиков X, Y (i=1..N)Все входные значения натуральные числа, не больше 100.

Выходные данные

    Единственное число - суммарная длина труб водопровода, округленная к целым

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, tmp1, tmp2, count_len;
float ans;
bool bv[100];
vector< pair<int, int> > v;
vector< pair<float, pair<int, int> > > len;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp1 >> tmp2;
        v.push_back(make_pair(tmp1, tmp2));
    }
    if (n == 1) { cout << 0 << endl; return 0; }
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            len.push_back(make_pair(hypot(v[i].first - v[j].first, v[i].second - v[j].second), make_pair(i, j)));

    sort(len.begin(), len.end());
    bv[len[0].second.first] = true;
    for (int i = 0; i < len.size(); i++)
    {
        if (count_len == n - 1) break;
        if (bv[len[i].second.first] ^ bv[len[i].second.second])
        {
            ans += len[i].first;
            bv[len[i].second.first] = bv[len[i].second.second] = true;
            i = 0;
        }
    }
    if (ans - int(ans) >= 0.5) ans += 1;
    cout << int(ans) << endl;
}

Назад

Повышение продаж с помощью веб-форм Разложение числа на простые множители Как качественный контент способствует продвижению сайта Как выбрать хостинг Как писать SEO-тексты? Что такое SEO оптимизация сайта


Хостинг

Есть решение которого нет на сайте? Пиши admin@devexe.top