camera_feli.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/**********************************************************************
Author: Felicia
Created Time:  2009-2-9 15:12:32
File Name: whu09_2.cpp
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

const double eps = 1e-9;

int sgn(const double &x) {
    return (x > eps) - (x < -eps);
}

struct point {
    double x, y, z;
    point() {}
    point(const double &_x, const double &_y, const double &_z) : x(_x), y(_y), z(_z) {}
    point operator +(const point &b) const {
        return point(x + b.x, y + b.y, z + b.z);
    }
    point operator -(const point &b) const {
        return point(x - b.x, y - b.y, z - b.z);
    }
    point operator *(const double &t) const {
        return point(x * t, y * t, z * t);
    }
    point operator /(const double &t) const {
        return point(x / t, y / t, z / t);
    }
    bool operator <(const point &b) const {
        return sgn(x - b.x) < 0 ||
               (sgn(x - b.x) == 0 && (sgn(y - b.y) < 0 ||
               (sgn(y - b.y) == 0 && sgn(z - b.z) < 0)));
    }
    bool operator ==(const point &b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0 && sgn(z - b.z) == 0;
    }
    double len2() const {
        return x * x + y * y + z * z;
    }
    double len() const {
        return sqrt(len2());
    }
    point tolen(const double &l) {
        double len = l / sqrt(len2());
        return point(x * len, y * len, z * len);
    }
    int read() {
        return scanf("%lf%lf%lf", &x, &y, &z);
    }
    void print() const {
        printf("(%lf %lf %lf)\n", x, y, z);
    }
};

double dot(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

double dot(const point &a, const point &b, const point &c) {
    return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y) + (b.z - a.z) * (c.z - a.z);
}

point cross(const point &a, const point &b) {
    return point(a.y * b.z - a.z * b.y,
               -(a.x * b.z - a.z * b.x),
                 a.x * b.y - a.y * b.x);
}

point cross(const point &a, const point &b, const point &c) {
    return point((b.y - a.y) * (c.z - a.z) - (b.z - a.z) * (c.y - a.y),
               -((b.x - a.x) * (c.z - a.z) - (b.z - a.z) * (c.x - a.x)),
                 (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}

double mixed(const point &a, const point &b, const point &c) {
    return dot(cross(a, b), c);
}

double volume(const point &p, const point &a, const point &b, const point &c) {
    return dot(a - p, cross(b - p, c - p));
}

bool inter_seg_tri(const point &p, const point &q,
                   const point &a, const point &b, const point &c, point &inter) {
    double v1 = volume(p, a, b, c);
    double v2 = volume(q, a, b, c);
    inter = (p * v2 - q * v1) / (v2 - v1);
    return sgn(v1) * sgn(v2) < 0 
        && sgn(dot(cross(inter, a, b), cross(inter, a, c))) <= 0
        && sgn(dot(cross(inter, b, c), cross(inter, b, a))) <= 0
        && sgn(dot(cross(inter, c, a), cross(inter, c, b))) <= 0;
}

bool inter_seg_tri_(const point &p, const point &q,
                   const point &a, const point &b, const point &c) {
    double v1 = volume(p, a, b, c);
    double v2 = volume(q, a, b, c);
    point inter = (p * v2 - q * v1) / (v2 - v1);
    return sgn(v1) * sgn(v2) < 0
        && sgn(dot(cross(inter, a, b), cross(inter, a, c))) < 0
        && sgn(dot(cross(inter, b, c), cross(inter, b, a))) < 0
        && sgn(dot(cross(inter, c, a), cross(inter, c, b))) < 0;
}


bool inner_point_camera(const point &p, const point &o, const point &a, const point &b, const point &c) {
    return sgn(volume(p, o, a, b)) > 0 && sgn(volume(p, o, b, c)) > 0 && sgn(volume(p, o, c, a)) > 0;
}

bool inter_seg_camera(const point &p, const point &q, const point &o, const point &a, const point &b, const point &c) {
    vector <point> t;
    point x;
    t.push_back(p);
    t.push_back(q);
    if (inter_seg_tri(p, q, o, a, b, x))
        t.push_back(x);
    if (inter_seg_tri(p, q, o, b, c, x))
        t.push_back(x);
    if (inter_seg_tri(p, q, o, c, a, x))
        t.push_back(x);
    sort(t.begin(), t.end());
    for (unsigned i = 0; i + 1 < t.size(); i++) {
        if (inner_point_camera((t[i] + t[i + 1]) / 2, o, a, b, c)) {
            return true;
        }
    }
    return false;
}

bool see_camera_tri(const point &o, const point &a, const point &b, const point &c,
                    const point &d, const point &e, const point &f) {
    if (inter_seg_camera(d, e, o, a, b, c) ||
        inter_seg_camera(e, f, o, a, b, c) ||
        inter_seg_camera(f, d, o, a, b, c))
        return true;
    if (inter_seg_tri_(o, (a + b + c) / 3, d, e, f)) {
        return true;
    }
    return false;
}

int main() {
    point o, a, b, c, d, e, f;
//    freopen("camera_feli.out", "w", stdout);
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        o.read();
        a.read();
        b.read();
        c.read();
        d.read();
        e.read();
        f.read();
        a = o + (a - o) * 10000;
        b = o + (b - o) * 10000;
        c = o + (c - o) * 10000;

        bool ret = see_camera_tri(o, a, b, c, d, e, f);
        if (ret)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}