1 条题解

  • 1
    @ 2022-8-31 9:19:31
    #include<cstdio>
    #include<cmath>
    #include<cstdlib> 
    #define EPS 1e-10
    //设EPS为1e-9时爆精度只得了75分,可能是脸黑
    struct Point
    {
    	double x,y,z;
    }point[105];
    int n;
    
    typedef Point Vector;
    
    double rand01()
    {
    	return rand()/(double)RAND_MAX;
    }
    
    double randeps()
    {
    	return (rand01()-0.5)*EPS;
    }
    
    Vector add_noise(Vector p)
    {
    	return (Vector){p.x+randeps(),p.y+randeps(),p.z+randeps()};
    }//生成一个一定EPS内的抖动
    
    Vector operator - (Vector a,Vector b)
    {
    	return (Vector){a.x-b.x,a.y-b.y,a.z-b.z};
    }//减法
    
    double mod(Vector a)
    {
    	return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
    }//模长
    
    double Dot(Vector a,Vector b)
    {
    	return a.x*b.x+a.y*b.y+a.z*b.z;
    }//点积,也就是数量积
    
    Vector Cross(Vector a,Vector b)
    {
    	return (Vector){a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};
    }//叉积,也就是向量积
    
    double area(Vector a,Vector b)
    {
    	return 0.5*mod(Cross(a,b));
    }//面积,叉积模长的一半
    
    bool check(int p1,int p2,int p3)
    {
    	double head=0,now;
    	Vector normal=Cross(point[p1]-point[p2],point[p2]-point[p3]);//将叉积作为法向量
    	for(int i=0;i<n;++i)
    	{
    		if(i!=p1&&i!=p2&&i!=p3)
    		{
    			if((now=Dot(point[i]-point[p1],normal))*head<0)
    			{//点积与余弦值一定同号
    				return false;
    			}
    			else
    			{
    				head=now;
    			}
    		}
    	}
    	return true;
    }
    
    int main()
    {
    	scanf("%d",&n);
    	double res=0;
    	for(int i=0;i<n;++i)
    	{
    		scanf("%lf %lf %lf",&point[i].x,&point[i].y,&point[i].z);
    		point[i]=add_noise(point[i]);//让点抖动一下
    	}
    	for(int i=0;i<n;++i)
    	{
    		for(int j=i+1;j<n;++j)
    		{
    			for(int k=j+1;k<n;++k)
    			{
    				if(check(i,j,k))
    				{//所有的点都在一侧
    					res+=area(point[i]-point[j],point[j]-point[k]);//就加上这个面的面积
    				}
    			}
    		}
    	}
    	printf("%.6lf",res);
    	return 0;
    }
    
    • 1

    信息

    ID
    1209
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    2
    上传者