URAL 2099 Space Invader 计算几何、卡精度、好题

Source

UESTC 2016 Summer Training #15 Div.2

URAL 2099

My Solution

先判断是否有向来垂直

然后判断 A到CD的距离 > B到CD的距离， 而且D到AB的距离 > C到AB的距离

然后判断是否 A B在CD的两边， 以及C、D是否在AB的两边

最后判断是否在一个平面， 用线性代数的方法

写的很辛苦， 写到后来， 自己都怕， 万一那个地方写错， 可能短时间内不大找的出来

然后就是最后判断 double 的相等的时候 把 a == b 搞错 fabs(a - b)  < 1e-6 或者更精确的eps

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    LL x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4;
    //!WA ?
    //!好吧 AB CD 必须按顺序， 直接判断 不能确定 BA 还是 AB了
    //!|AD| > |BC|不对
    //!A到 CD的距离比B的大， D到AB的距离比C大 ^_^
    scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &x1, &y1, &z1, &x2, &y2, &z2, &x3, &y3, &z3, &x4, &y4, &z4);
    //cout<<(x1 - x2)*(x3 - x4) + (y1 - y2)*(y3 - y4) + (z1 - z2)*(z3 - z4)<<endl;
    double m = x1 - x2, n = y1 - y2, p = z1 - z2;
    double t = (m*(x3-x1)+n*(y3-y1)+p*(z3-z1))/(m*m+n*n+p*p);
    double xc = m*t+x1, yc = n*t+y1, zc = p*t+z1;
    double d1 = sqrt((x3-xc)*(x3-xc)*1.0+(y3-yc)*(y3-yc)*1.0+(z3-zc)*(z3-zc)*1.0);

    t = (m*(x4-x1)+n*(y4-y1)+p*(z4-z1))/(m*m+n*n+p*p);
    xc = m*t+x1, yc = n*t+y1, zc = p*t+z1;
    double d2 = sqrt((x4-xc)*(x4-xc)*1.0+(y4-yc)*(y4-yc)*1.0+(z4-zc)*(z4-zc)*1.0);

    m = x3 - x4, n = y3 - y4, p = z3 - z4;
    t = (m*(x1-x3)+n*(y1-y3)+p*(z1-z3))/(m*m+n*n+p*p);
    xc = m*t+x3, yc = n*t+y3, zc = p*t+z3;
    double d3 = sqrt((x1-xc)*(x1-xc)*1.0+(y1-yc)*(y1-yc)*1.0+(z1-zc)*(z1-zc)*1.0);

    t = (m*(x2-x3)+n*(y2-y3)+p*(z2-z3))/(m*m+n*n+p*p);
    xc = m*t+x3, yc = n*t+y3, zc = p*t+z3;
    double d4 = sqrt((x2-xc)*(x2-xc)*1.0+(y2-yc)*(y2-yc)*1.0+(z2-zc)*(z2-zc)*1.0);
    //WA......
    //cout<<"d1 "<<d1<<" d2 "<<d2<<" d3 "<<d3<<" d4 "<<d4<<endl;
    double dadb = sqrt((x2-x1)*(x2-x1)*1.0+(y2-y1)*(y2-y1)*1.0+(z2-z1)*(z2-z1)*1.0);
    double dddc = sqrt((x4-x3)*(x4-x3)*1.0+(y4-y3)*(y4-y3)*1.0+(z4-z3)*(z4-z3)*1.0);
    //希望精度损失不是很严重


    if((x1 - x2)*(x3 - x4) + (y1 - y2)*(y3 - y4) + (z1 - z2)*(z3 - z4) == 0){   //! 1) 垂直
        if(d1 < d2 && d3 > d4){                                                 //! 2) 依次过ABCD
            if(fabs(d2 - d1 - dddc) < 1e-6 && fabs(d3 - d4 - dadb) < 1e-6){                             //! 2) 依次过ABCD  希望这个方法靠谱
                double a = ((y2-y1)*(z3-z1)-(z2-z1)*(y3-y1));
                double b = ((z2-z1)*(x3-x1)-(x2-x1)*(z3-z1));
                double c = ((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1));                   //! 3) 三点共面
                if(fabs(a*(x4 - x3) + b*(y4 - y3) + c*(z4 - z3)) < 1e-6) printf("Valid");
                else printf("Invalid");

            }
            else printf("Invalid");
        }
        else printf("Invalid");
    }
    else printf("Invalid");



    #ifdef LOCAL
    printf("n");
    }
    #endif // LOCAL
    return 0;
}