首页 > 代码库 > NYOJ 78 圈水池 （入门级凸包）
NYOJ 78 圈水池 （入门级凸包）
题目链接：nyoj 78
题目讲解：本题考查的主要是凸包的用法，算是入门级的吧，当然前提是你接触过，平面几何：
AC代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<vector> 6 using namespace std; 7 struct T 8 { 9 int x,y;10 friend int operator < (T a, T b)11 {12 if((a.x<b.x) || (a.x==b.x && a.y<b.y))13 return 1;14 return 0;15 }16 }a[105],ans[105];17 //用来判断第三点在当前两点构成的直线的左侧还是右侧，右侧返回值小于0；18 double judge(T a, T b,T c)19 {20 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);21 }22 int main()23 {24 int T,m;25 scanf("%d",&T);26 while(T--)27 {28 29 scanf("%d",&m);30 for(int i=0; i<m; i++)31 {32 scanf("%d %d",&a[i].x,&a[i].y);33 }34 sort(a,a+m);35 int k1=0;36 for(int i=0; i<m; i++)//下凸包，从下面扫描个点；37 {38 while(k1>1 && judge(ans[k1-2],ans[k1-1],a[i])<=0)39 {40 k1--;41 }42 ans[k1++]=a[i];43 }44 int k2=k1;45 for(int i=m-1; i>=0; i--)//上凸包，从上面扫描各点；46 {47 while(k1>k2 && judge(ans[k1-2],ans[k1-1],a[i])<=0)48 {49 k1--;50 }51 ans[k1++]=a[i];52 }53 k1--;54 sort(ans,ans+k1);55 for(int i=0; i<k1; i++)56 printf("%d %d\n",ans[i].x,ans[i].y);57 }58 return 0;59 }
NYOJ 78 圈水池 （入门级凸包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。