本文主要是介绍Codeforces Beta Round #47 C凸包 （最终写法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意慢慢看。
typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;
}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point operator - (const point &o){return point(x - o.x , y - o.y) ;}friend double operator ^ (const point &a , const point &b){return a.x * b.y - a.y * b.x ;}friend bool operator < (const point &a , const point &b){if(cmp(a.x - b.x) != 0) return cmp(a.x - b.x) < 0 ;else return cmp(a.y - b.y) < 0 ;}friend bool operator == (const point &a , const point &b){return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0 ;}friend LL dist(const point &a , const point &b){return (LL) max( fabs(a.x - b.x) , fabs(a.y - b.y)) ;}
};vector<point> convex_hull(vector<point> a){vector<point> s(a.size() * 2 + 5) ;sort(a.begin() , a.end()) ;a.erase( unique(a.begin() , a.end()) , a.end()) ;int m = 0 ;for(int i = 0 ; i < a.size() ; i++){while(m > 1 && cmp((s[m-1] - s[m-2]) ^ (a[i] - s[m-2])) < 0) m-- ;s[m++] = a[i] ;}int k = m ;for(int i = a.size() - 2 ; i >= 0 ; i--){while(m > k && cmp((s[m-1] - s[m-2]) ^ (a[i] - s[m-2])) < 0) m-- ;s[m++] = a[i] ;}s.resize(m) ;if(a.size() > 1) s.resize(m-1) ;return s ;
}int main(){int i , n ;double x , y ;vector<point> lis ;cin>>n;for(i = 0 ; i < n ; i++){scanf("%lf%lf" , &x , &y) ;lis.push_back(point(x-1 , y)) ;lis.push_back(point(x+1 , y)) ;lis.push_back(point(x , y-1)) ;lis.push_back(point(x , y+1)) ;}vector<point> hull = convex_hull(lis) ;LL ans = 0 ;for(i = 0 ; i < hull.size() ; i++)ans += dist(hull[i] , hull[(i+1) % hull.size()]) ;cout<< ans << endl ;return 0 ;
}
这篇关于Codeforces Beta Round #47 C凸包 （最终写法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
