Почему мой расчетный периметр корпуса не работает?

Question

Input: набор точек Выход: периметр выпуклой оболочки из этих точек

Я не знаю почему, но я все еще получаю плохой периметр на некоторых входах (я не знаю, какие входы). Не могли бы вы рассказать мне, есть ли что-то плохое в моем alghorithm? (Или реализации)

#include<iostream> 
#include<vector> 
#include<algorithm> 
#include<cmath> 
#include<iomanip> 
using namespace std; 


struct Point{ 
    int x; 
    int y; 

    bool operator<(const Point &p)const 
    { 
    return (x<p.x || (x==p.x && y<p.y)); 
    } 
}; 

long long cross(Point A, Point B, Point C) 
    { 
     return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); 
    } 



vector<Point> ConvexHull(vector<Point> P) //Andrew's monotone chain 
    { 
    vector<Point> H; //hull 
    H.resize(2*P.size()); 

    int k=0; 

    if(P.size()<3) return H; 
    sort(P.begin(),P.end()); 

    //lower 
    for(int i=0;i<P.size();i++) 
    { 
     while(k>=2 && cross(H[k-2],H[k-1],P[i])<=0) 
      k--; 
     H[k]=P[i]; 
     k++;   
    } 

    int t=k+1; 

    //upper 
    for(int i=P.size()-2; i>=0 ;i--) 
    { 
     while(k>=t && cross(H[k-2],H[k-1],P[i])<=0) 
      k--; 
     H[k]=P[i]; 
     k++; 
    } 


    H.resize(k); 
    return H; 
}; 

double perimeter(vector<Point> P) 
{ 
    double r=0; 
    for(int i=1;i<P.size();i++) 
     r+=sqrt(pow(P[i].x-P[i-1].x,2)+pow(P[i].y-P[i-1].y,2)); 
    return r; 
} 


int main(){ 
     int N; 
     cin>>N; 
     vector<Point>P; 
     P.resize(N); 

     for(int i=0;i<N;i++) 
      cin>>P[i].x>>P[i].y; 

     vector<Point>H; 
     H=ConvexHull(P); 

     cout<<setprecision(9)<<perimeter(H)<<endl; 
     //system("pause"); 
     return 0; 
}; 

Answer 1

Предполагая, что алгоритм верен, я полагаю: вы работаете на 32 бит и получаете переполнение целого числа.

Answer 2

Вы не должны добавить код ниже после того, как цикл в функции периметра:

r += sqrt(pow(P[P.size() - 1].x-P[0].x,2)+pow(P[P.size() - 1].y-P[0].y,2)); 

Вы хотите добавить расстояние между первой и последней точкой в выпуклая оболочка.