首页 > 代码库 > poj1113Wall 求凸包周长 Graham扫描法
poj1113Wall 求凸包周长 Graham扫描法
#include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef pair<int ,int > ll; ll num,dot[1010]; int i; const double pi=3.1415926535898; ll operator -(ll a,ll b) { return make_pair(a.first-b.first,a.second-b.second); } bool cmp(ll a,ll b) { return (a.first!=b.first?a.first<b.first:a.second<b.second); } int cross(ll a,ll b) { return a.first*b.second-b.first*a.second; } int d2(ll a,ll b) { return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); } double d1(ll a,ll b) { return sqrt((double)d2(a,b)); } bool cmp1(ll a,ll b) { int r=cross(a-dot[0],b-dot[0]); return (r!=0?r>0:d2(a,dot[0])<d2(b,dot[0])); } void in() { cin>>num.first>>num.second; for(i=0;i<num.first;i++) cin>>dot[i].first>>dot[i].second; } void work() { sort(dot,dot+num.first,cmp); sort(dot,dot+num.first,cmp1); ll box[1010]={dot[0],dot[1]}; int tail=1; for(i=2;i<num.first;) { if(cross(box[tail]-box[tail-1],dot[i]-box[tail-1])>=0) box[++tail]=dot[i++]; else tail--; } double ans=d1(box[0],box[tail])+2*pi*num.second; for(i=0;i<tail;i++) ans+=d1(box[i],box[i+1]); printf("%.0lf\n",ans); } int main() { in(); work(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。