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;
		else
		cout<<(n*n*2-n+1)<<endl;
	}
	return 0;
}