本文主要是介绍7.26 练习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
E题
POJ 3348 Cows(凸包求面积) 题目链接http://poj.org/problem?id=3348
| 相关知识 Andrew算法：Andrew算法是一种基于水平序的算法，在许多的资料上都会发现说该算法可以看作Graham扫描法的一种变体。 二者都是对所有的点进行扫描得到凸包，不过扫描之前做的处理不同，Andrew算法的大致流程如下： ①将所有的点按照横坐标从小到大进行排序，横坐标相同则按纵坐标从小到大排； ②将P[0]和P[1]加入凸包，然后从P[2]开始判断，判断方式同Graham算法中的判断一致； 然后把点1和点2放入凸包的栈中，然后从p3开始当新的点在凸包前进的方向的左边时加入并继续，否则说明方向已经向内凹了，此时依次删除当时在栈顶的点，直至新点在左边。 此时新点E方向在向量CD的右边，所以需要在凸包的栈中删除C和D,让B的下一个点为E，重复此过程，直至碰到最右边的pn,求出了凸包下部分，然后反过来求出凸包的上部分，合起来求得完整的凸包。
③将所有的点扫描一遍以后，我们便可以得到一个“下凸包”（因为-横坐标不会减小）； ④同理，我们从P[n-2]开始(P[n-1]已经判过了)，反着扫描一遍，便可以得到一个“上凸包”； ⑤将两个“半凸包”合在一起就是一个完整的凸包，注意的是由于起点P[0]在正着扫描和反着扫描时都会将其加入凸包，故需要将最后一个点(P[0])去掉才为最终结果。 |
AC code：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;//精度控制
const double eps=1e-10;
int dcmp(double x)
{if(fabs(x)<eps) return 0;else return x<0?-1:1;
}//点
struct point
{double x,y;point(){}point(double x,double y):x(x),y(y){}bool operator==(const point& rhs)const{return dcmp(x-rhs.x)==0 && dcmp(y-rhs.y)==0;}bool operator<(const point& rhs)const{return dcmp(x-rhs.x)<0 || (dcmp(x-rhs.x)==0 && dcmp(y-rhs.y)==0);}
};bool cmp(point a,point b)
{if(a.x==b.x) return a.y<b.y;else return a.x<b.x;
}//向量
typedef point Vector;//点-点==向量
Vector operator-(point A,point B) //operator运算
{return Vector(A.x-B.x,A.y-B.y);//Vector向量
}//叉积
double Cross(Vector A,Vector B)
{return A.x*B.y-A.y*B.x;
}//多边形面积
double PolygonArea(point *p,int n)
{double area=0;for(int i=1;i<n-1;i++)area+= Cross(p[i]-p[0],p[i+1]-p[0]);return fabs(area)/2;
}//凸包ConvexHull的 Andrew算法
//计算凸包，输入点数组p，个数为n，输出点数组ch。函数返回凸包顶点数。
//输入不能有重复点，函数执行完成之后输入点的顺序被破坏。
//如果不希望凸包的边上有输入点，把两个 <= 改成 <
int ConvexHull ( point * p,int n, point * ch )
{//sort (p,p+n,cmp ); sort (p,p+n);//按先比x再比y的顺序排序int m=0;for (int i=0;i<n;i ++)//从左到右扫描{while (m >1&& Cross(ch[m -1] - ch[m -2] ,p[i]-ch[m -2]) <=0) //det:叉积 m --;ch[m ++]= p[i];}int k=m;for (int i=n -2;i >=0;i--)//从右到左扫描{while (m>k&& Cross(ch[m -1] - ch[m -2] ,p[i]-ch[m -2]) <=0) m --;ch[m ++]= p[i];}if(n >1) m--;return m;//m为凸包顶点个数
}const int maxn=10000+5;
point p[maxn],ch[maxn];
int main()
{int n;while(scanf("%d",&n)==1){for(int i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);int m=ConvexHull(p,n,ch);double area=PolygonArea(ch,m);printf("%d\n",(int)area/50);}return 0;
}G题 水
H题 水
I题 折线分割平面
#include<iostream>
using namespace std;
int main()
{int c,n;cin>>c;while(c--){cin>>n;if(n==0)cout<<"1"<<endl;else if(n==1)cout<<"2"<<endl;else if(n==2)cout<<"7"<<endl;elsecout<<(n*n*2-n+1)<<endl;}return 0;
}
这篇关于7.26 练习题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
