欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7.26 练习题

程序员文章站 2022-04-03 17:13:18
...

E题

POJ 3348 Cows(凸包求面积)  题目链接http://poj.org/problem?id=3348

相关知识

Andrew算法:

Andrew算法是一种基于水平序的算法,在许多的资料上都会发现说该算法可以看作Graham扫描法的一种变体。

二者都是对所有的点进行扫描得到凸包,不过扫描之前做的处理不同,Andrew算法的大致流程如下:

①将所有的点按照横坐标从小到大进行排序,横坐标相同则按纵坐标从小到大排;

②将P[0]和P[1]加入凸包,然后从P[2]开始判断,判断方式同Graham算法中的判断一致;

然后把点1和点2放入凸包的栈中,然后从p3开始当新的点在凸包前进的方向的左边时加入并继续,否则说明方向已经向内凹了,此时依次删除当时在栈顶的点,直至新点在左边。

7.26 练习题

此时新点E方向在向量CD的右边,所以需要在凸包的栈中删除C和D,让B的下一个点为E,重复此过程,直至碰到最右边的pn,求出了凸包下部分,然后反过来求出凸包的上部分,合起来求得完整的凸包。

 

7.26 练习题

③将所有的点扫描一遍以后,我们便可以得到一个“下凸包”(因为-横坐标不会减小);

④同理,我们从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;
}