本文主要是介绍HDU 1392 HDU 1348 凸包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求凸包的周长， 注意n=1 ， 2时特殊情况
int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;
}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}friend bool operator == (const point &a , const point &b){return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0 ;}friend double operator ^ (const point &a , const point &b){return a.x * b.y - a.y * b.x ;}friend double dist(const point &a , const point &b){return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) ;}point operator - (point o){return point(x - o.x , y - o.y) ;}
};bool cmpless(const point &a , const point &b){return cmp(a.x - b.x) < 0|| cmp(a.x - b.x == 0) && cmp(a.y - b.y) < 0 ;
}vector<point> convex_hull(vector<point> a){vector<point> src(2 * a.size() + 5) ;sort(a.begin() , a.end() , cmpless) ;a.erase(unique(a.begin() , a.end()) , a.end()) ;int m = 0 ;for(int i = 0 ; i < a.size() ; i++){while(m > 1 && cmp( (src[m-1] - src[m-2]) ^ (a[i] - src[m-2]) ) <= 0)m-- ;src[m++] = a[i] ;}int k = m ;for(int i = a.size() - 2 ; i >= 0 ; i--){while(m > k && cmp( (src[m-1] - src[m-2]) ^ (a[i] - src[m-2])) <= 0)m-- ;src[m++] = a[i] ;}src.resize(m) ;if(a.size() > 1) src.resize(m-1) ;return src ;
}int main(){int n , i ;double ans ;while(cin>>n && n){vector<point> lis(n) ;for(i = 0 ; i < n ; i++)scanf("%lf%lf" , &lis[i].x , &lis[i].y) ;if(n == 1) ans = 0.0 ;else if(n == 2) ans = dist(lis[0] , lis[1]) ;else{vector<point> a = convex_hull(lis) ;ans = 0.0 ;for(i = 0 ; i < a.size() ; i++)ans += dist(a[i] , a[(i+1) % a.size()]) ;}printf("%.2lf\n" , ans) ;}return 0 ;
}hdu 1348
int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;
}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}friend bool operator == (const point &a , const point &b){return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0 ;}friend double operator ^ (const point &a , const point &b){return a.x * b.y - a.y * b.x ;}friend double dist(const point &a , const point &b){return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) ;}point operator - (point o){return point(x - o.x , y - o.y) ;}
};bool cmpless(const point &a , const point &b){return cmp(a.x - b.x) < 0|| cmp(a.x - b.x == 0) && cmp(a.y - b.y) < 0 ;
}vector<point> convex_hull(vector<point> a){vector<point> src(2 * a.size() + 5) ;sort(a.begin() , a.end() , cmpless) ;a.erase(unique(a.begin() , a.end()) , a.end()) ;int m = 0 ;for(int i = 0 ; i < a.size() ; i++){while(m > 1 && cmp( (src[m-1] - src[m-2]) ^ (a[i] - src[m-2]) ) <= 0)m-- ;src[m++] = a[i] ;}int k = m ;for(int i = a.size() - 2 ; i >= 0 ; i--){while(m > k && cmp( (src[m-1] - src[m-2]) ^ (a[i] - src[m-2])) <= 0)m-- ;src[m++] = a[i] ;}src.resize(m) ;if(a.size() > 1) src.resize(m-1) ;return src ;
}int main(){int n , i , t , T = 1 ;double ans , r ;cin>>t ;while(t--){cin>>n>>r ;vector<point> lis(n) ;for(i = 0 ; i < n ; i++)scanf("%lf%lf" , &lis[i].x , &lis[i].y) ;if(n == 1) ans = 0.0 ;else if(n == 2) ans = dist(lis[0] , lis[1]) ;else{vector<point> a = convex_hull(lis) ;ans = 0.0 ;for(i = 0 ; i < a.size() ; i++)ans += dist(a[i] , a[(i+1) % a.size()]) ;}if(T++ != 1) puts("") ;printf("%.0lf\n" , ans + 2.0 * acos(-1.0) * r) ;}return 0 ;
}
这篇关于HDU 1392 HDU 1348 凸包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
