Как найти периметр выпуклой оболочки и почему расстояния тут лучше считать в double, а сравнения — в целых?
Построил выпуклую оболочку, теперь нужно вернуть её периметр (сумму длин рёбер). Тут уже не сравнение, а конкретная числовая величина с корнями. Как аккуратно посчитать и где целые числа всё ещё помогают?
2 ответа
Периметр — это сумма евклидовых длин рёбер, и тут sqrt неизбежен, потому что нужна сама величина, а не сравнение. Но квадраты длин держим целыми до момента корня:
double hullPerimeter(const vector<P>& h) {
int n = h.size();
double per = 0;
for (int i = 0; i < n; i++) {
P a = h[i], b = h[(i + 1) % n];
long long d2 = (b - a).len2(); // целочисленный квадрат длины ребра
per += sqrt((double)d2);
}
return per;
}
Где целые помогают: каждый len2() считается точно в long long, и только перед сложением переводится в double через sqrt. Это минимизирует накопление ошибки — ты не делаешь промежуточных дробных операций, только финальный корень на ребро. Сложность O(n).
Ключевая мысль: разделяй «решающие» вычисления (построение оболочки, ориентации — целочисленно, точно) и «измерительные» (длины, периметр, площадь в дробях — double в самом конце). Так точность теряется только там, где это неизбежно по сути задачи.
Дополнение про точность суммы. Если рёбер очень много и длины сильно разного масштаба, сумма double может накопить ошибку. Лечится long double для аккумулятора или суммированием по Кэхэну — но на типичных олимпиадных ограничениях обычного double/long double хватает с запасом.
И важный смежный момент: площадь оболочки, в отличие от периметра, корня не требует — её считают шнуровкой в целых (area2/2), и вот её эталонно держат целочисленной до самого деления на 2. Так что периметр и площадь — хороший пример того, что одни геометрические величины принципиально дробные (нужен sqrt), а другие — целые, и смешивать их подходы не стоит.