camera_lzx.java

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

import java.io.*;
import java.math.*;
import java.util.*;

class Point {
    double x, y, z;
    Point(double _x, double _y, double _z) {
        x = _x;
        y = _y;
        z = _z;
    }
    Point add(Point p) {
        return new Point(x + p.x, y + p.y, z + p.z);
    }
    Point sub(Point p) {
        return new Point(x - p.x, y - p.y, z - p.z);
    }
    Point mul(double t) {
        return new Point(x * t, y * t, z * t);
    }
    Point div(double t) {
        return new Point(x / t, y / t, z / t);
    }
}

public class Camera {
    private double epsilon = 1e-10;
    int dcmp(double x) {
        if (Math.abs(x) < epsilon) return 0;
        return x > epsilon ? +1 : -1;
    }
    double dot(Point a, Point b) {
        return a.x * b.x + a.y * b.y + a.z * b.z;
    }
    Point cross(Point a, Point b) {
        return new Point(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 volume(Point o, Point a, Point b, Point c) {
        return dot(cross(a.sub(o), b.sub(o)), c.sub(o));
    }
    boolean inner(Point p, Point o, Point a, Point b, Point c) {
        int x0 = dcmp(volume(p, o, a, b));
        int x1 = dcmp(volume(p, o, b, c));
        int x2 = dcmp(volume(p, o, c, a));
        return x0 > 0 && x1 > 0 && x2 > 0;
    }
    boolean opposite(Point s, Point t, Point a, Point b, Point c) {
        double sign = volume(s, a, b, c) * volume(t, a, b, c);
        return dcmp(sign) < 0;
    }
    boolean intersect(Point s, Point t, Point a, Point b, Point c) {
        boolean x0 = opposite(s, t, a, b, c);
        boolean x1 = opposite(a, b, s, t, c);
        boolean x2 = opposite(b, c, s, t, a);
        boolean x3 = opposite(c, a, s, t, b);
        return x0 == true && x1 == true && x2 == true && x3 == true;
    }
    double dist(Point a, Point b) {
        return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
    }
    double area(double a, double b, double c) {
        double p = (a + b + c) / 2;
        return Math.sqrt(p * (p - a) * (p - b) * (p - c));
    }
    boolean in_triangle(Point p, Point a, Point b, Point c) {
        double pa = dist(p, a), pb = dist(p, b), pc = dist(p, c);
        double ab = dist(a, b), bc = dist(b, c), ca = dist(c, a);
        double pab = area(pa, pb, ab), pbc = area(pb, pc, bc), pca = area(pc, pa, ca);
        double abc = area(ab, bc, ca);
        double res = Math.abs(abc - pab - pbc - pca);
        return res < epsilon;
    }
    boolean intersect_point(Point s, Point t, Point a, Point b, Point c, Point p) {
        double s1 = volume(s, a, b, c), s2 = volume(t, a, b, c);
        if (dcmp(s1) * dcmp(s2) > 0) return false;
        double alpha = Math.abs(s1) / (Math.abs(s1) + Math.abs(s2));
        p = s.add((t.sub(s)).mul(alpha));
        if (in_triangle(p, a, b, c)) return true;
        return false;
    }
    boolean cmp(Point a, Point b) {
        if (Math.abs(a.x - b.x) < epsilon && Math.abs(a.y - b.y) < epsilon) return a.z < b.z;
        if (Math.abs(a.x - b.x) < epsilon) return a.y < b.y;
        return a.x < b.x;
    }
    class cmp implements Comparator {
        public int compare(Object ia, Object ib) {
            Point a = (Point) ia, b = (Point) ib;
            if (Math.abs(a.x - b.x) < epsilon && Math.abs(a.y - b.y) < epsilon) {
                return dcmp(a.z - b.z);
            }
            if (Math.abs(a.x - b.x) < epsilon) {
                return dcmp(a.y - b.y);
            }
            return dcmp(a.x - b.x);
        }
    }
    boolean collid(Point s, Point t, Point o, Point a, Point b, Point c) {
        Point[] it = new Point[64];
        int cnt = 0;
        Point p = new Point(0, 0, 0);
        if (intersect_point(s, t, o, a, b, p)) {
            it[cnt++] = p;
        }
        if (intersect_point(s, t, o, b, c, p)) {
            it[cnt++] = p;
        }
        if (intersect_point(s, t, o, c, a, p)) {
            it[cnt++] = p;
        }
        it[cnt++] = s;
        it[cnt++] = t;
        Arrays.sort(it, 0, cnt, new cmp());
        for (int i = 0; i < cnt - 1; ++i) {
            if (inner((it[i].add(it[i + 1])).div(2), o, a, b, c)) {
                return true;
            }
        }
        return false;
    }
    boolean intersect(Point o, Point a, Point b, Point c, Point d, Point e, Point f) {
        if (inner(d, o, a, b, c) || inner(e, o, a, b, c) || inner(f, o, a, b, c)) {
            return true;
        }
        if (intersect(d, e, o, a, b) || intersect(d, e, o, b, c) || intersect(d, e, o, c, a)) {
            return true;
        }
        if (intersect(e, f, o, a, b) || intersect(e, f, o, b, c) || intersect(e, f, o, c, a)) {
            return true;
        }
        if (intersect(f, d, o, a, b) || intersect(f, d, o, b, c) || intersect(f, d, o, c, a)) {
            return true;
        }
        if (intersect(o, ((a.add(b)).add(c)).div(3), d, e, f)) {
            return true;
        }
        if (collid(d, e, o, a, b, c) || collid(e, f, o, a, b, c) || collid(f, d, o, a, b, c)) {
            return true;
        }
        return false;
    }
    private final int Length = 10000;
    void run() throws IOException {
        //        Scanner in = new Scanner(new File("camera.in"));
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        double x, y, z;
        for (int i = 0; i < T; ++i) {

            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point o = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point a = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point b = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point c = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point d = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point e = new Point(x, y, z);
            x = in.nextDouble(); y = in.nextDouble(); z = in.nextDouble();
            Point f = new Point(x, y, z);

            a = a.add((a.sub(o)).mul(Length));
            b = b.add((b.sub(o)).mul(Length));
            c = c.add((c.sub(o)).mul(Length));

            if (intersect(o, a, b, c, d, e, f)) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
    public static void main(String[] args) throws IOException {
        new Camera().run();
    }
}