loj6063 Shadow

题目描述

题解：

显然凸多面体投下来一定是个凸多边形。

对于$30$分，直接投到$x-y$平面上即可。

对于$100$分，考虑搞出平面的一般式方程$ax+by+cz+d=0$。

给出平面上三个点$A,B,C$，那么求$(B-A)$^$(C-A)$，得到向量$(a,b,c)$，

然后随便带一个点把$d$求出来即可。

接下来把所有凸多边形顶点投影到平面上，接下来向$x-y$投影。

$x-y$平面上算出的面积与所求面积成比例。

比值即为$S(A,B,C)/S(A_0,B_0,C_0)$，计算三角形面积用海伦公式即可。

没卡我精度好爽。

代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps = 1e-6;
double A,B,C,D;
struct SPoint
{
    double x,y,z;
    SPoint(){}
    SPoint(double x,double y,double z):x(x),y(y),z(z){}
    SPoint operator - (const SPoint&a)const{return SPoint(x-a.x,y-a.y,z-a.z);}
    SPoint operator ^ (const SPoint&a)const{return SPoint(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);}
    void read(){scanf("%lf%lf%lf",&x,&y,&z);}
}a,b,c,a0,b0,c0;
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    bool operator < (const Point&a)const{return x!=a.x?x+eps<a.x:y+eps<a.y;}
    Point operator - (const Point&a)const{return Point(x-a.x,y-a.y);}
    double operator ^ (const Point&a)const{return x*a.y-y*a.x;}
}p[105],v1[105],v2[105];
void init()
{
    a.read(),b.read(),c.read();
    a0=a,b0=b,c0=c;
    a0.z=b0.z=c0.z=0;
    SPoint tmp = (b-a)^(c-a);
    A=tmp.x,B=tmp.y,C=tmp.z;
    D=-1.0*(A*a.x+B*a.y+C*a.z);
}
int n,t1,t2;
double xx,yy,zz;
void mov(double&x,double&y,double&z)
{
    double dx = xx-x,dy = yy-y,dz = zz-z;
    double k = -1.0*(A*x+B*y+C*z+D)/(A*dx+B*dy+C*dz);
    x = x+k*dx;
    y = y+k*dy;
    z = z+k*dz;
}
double S(double a,double b,double c)
{
    double P = (a+b+c)/2.0;
    return sqrt(P*(P-a)*(P-b)*(P-c));
}
double sq(double x){return x*x;}
double L(SPoint a,SPoint b)
{
    return sqrt(sq(a.x-b.x)+sq(a.y-b.y)+sq(a.z-b.z));
}
double K()
{
    return S(L(a,b),L(a,c),L(b,c))/S(L(a0,b0),L(a0,c0),L(b0,c0));
}
int main()
{
    init();
    scanf("%lf%lf%lf",&xx,&yy,&zz);
    scanf("%d",&n);
    double x,y,z;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&x,&y,&z);
        mov(x,y,z);
        p[i]=Point(x,y);
    }
    sort(p+1,p+1+n);
    for(int i=1;i<=n;i++)
    {
        while(t1>1&&((v1[t1]-v1[t1-1])^(p[i]-v1[t1]))>=0)t1--;
        v1[++t1]=p[i];
        while(t2>1&&((v2[t2]-v2[t2-1])^(p[i]-v2[t2]))<=0)t2--;
        v2[++t2]=p[i];
    }
    double ans = 0;
    for(int i=3;i<=t1;i++)ans-=((v1[i-1]-v1[1])^(v1[i]-v1[i-1]));
    for(int i=3;i<=t2;i++)ans+=((v2[i-1]-v2[1])^(v2[i]-v2[i-1]));
    printf("%.2lf
",K()*ans/2.0);
    return 0;
}