gym 100531 三维几何+搜索

精度有点毒， 其实可以不用double， 因为A, B必定在其中一个在三角形上，可以投影到只有x，y轴的地方叉积比较。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define PLL pair<LL, LL>
#define ull unsigned long long
using namespace std;

const int N = 5000 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-4;

int dcmp(double x) {
    if(fabs(x) <= eps) return 0;
    return x < 0 ? -1 : 1;
}

struct Point3 {
    double x, y, z;
    Point3(double x=0, double y=0, double z=0):x(x), y(y), z(z) {}
    bool operator < (const Point3 &rhs) const {
        if(x == rhs.x && y == rhs.y) return z < rhs.z;
        else if(x == rhs.x) return y < rhs.y;
        else return x < rhs.x;
    }
    bool operator == (const Point3 &rhs) const {
        return dcmp(x-rhs.x)==0 && dcmp(y-rhs.y) == 0 && dcmp(z-rhs.z == 0);
    }
};

typedef Point3 Vector3;

Vector3 operator + (Vector3 A, Vector3 B) {
    return Vector3(A.x+B.x, A.y+B.y, A.z+B.z);
}
Vector3 operator - (Vector3 A, Vector3 B) {
    return Vector3(A.x-B.x, A.y-B.y, A.z-B.z);
}
Vector3 operator * (Vector3 A, double p) {
    return Vector3(A.x*p, A.y*p, A.z*p);
}
Vector3 operator / (Vector3 A, double p) {
    return Vector3(A.x/p, A.y/p, A.z/p);
}
double Dot(Vector3 A, Vector3 B) {
    return A.x*B.x + A.y*B.y + A.z*B.z;
}
double Length(Vector3 A) {
    return sqrt(Dot(A, A));
}
double Angle(Vector3 A, Vector3 B) {
    return acos(Dot(A, B)/Length(A)/Length(B));
}
Vector3 Cross(Vector3 A, Vector3 B) {
    return Vector3(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 Area2(Point3 A, Point3 B, Point3 C) {
    return Length(Cross(B-A, C-A));
}
bool PointInTri(Point3 P, Point3 P0, Point3 P1, Point3 P2) {
    double area1 = Area2(P, P0, P1);
    double area2 = Area2(P, P1, P2);
    double area3 = Area2(P, P2, P0);
    return dcmp(area1+area2+area3-Area2(P0, P1, P2)) == 0;
}

int n, tot, who1, who2;
Point3 tri[N][3], a[N*3], A, B;
vector<int> edge[N*3];
vector<int> path, tmp, ans;
bool vis[N*3];

inline int getId(Point3 &p) {
    return lower_bound(a+1, a+1+tot, p)-a;
}

void dfs(int u, bool &flag, double up) {
    if(flag) return;
    vis[u] = true;
    path.push_back(u);
    if(u == who2) {
        tmp = path;
        flag = true;
    }
    for(int v : edge[u]) {
        if(vis[v] || a[v].z > up) continue;
        dfs(v, flag, up);
    }
    path.pop_back();
}

bool check(double up) {
    bool flag = false;
    memset(vis, 0, sizeof(vis));
    dfs(who1, flag, up);
    return flag;
}

int main() {
    freopen("hiking.in", "r", stdin);
    freopen("hiking.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 3; j++) {
            scanf("%lf%lf%lf", &tri[i][j].x, &tri[i][j].y, &tri[i][j].z);
            a[++tot] = tri[i][j];
        }
    }
    scanf("%lf%lf%lf", &A.x, &A.y, &A.z);
    scanf("%lf%lf%lf", &B.x, &B.y, &B.z);
    a[++tot] = A; a[++tot] = B;
    sort(a+1, a+1+tot);
    tot = unique(a+1, a+1+tot)-a-1;
    who1 = getId(A); who2 = getId(B);
    for(int i = 1; i <= n; i++) {
        int id0 = getId(tri[i][0]);
        int id1 = getId(tri[i][1]);
        int id2 = getId(tri[i][2]);
        edge[id0].push_back(id1);
        edge[id1].push_back(id0);
        edge[id0].push_back(id2);
        edge[id2].push_back(id0);
        edge[id1].push_back(id2);
        edge[id2].push_back(id1);
        if(PointInTri(A, tri[i][0], tri[i][1], tri[i][2])) {
            edge[who1].push_back(id0);
            edge[who1].push_back(id1);
            edge[who1].push_back(id2);
            edge[id0].push_back(who1);
            edge[id1].push_back(who1);
            edge[id2].push_back(who1);
        }
        if(PointInTri(B, tri[i][0], tri[i][1], tri[i][2])) {
            edge[who2].push_back(id0);
            edge[who2].push_back(id1);
            edge[who2].push_back(id2);
            edge[id0].push_back(who2);
            edge[id1].push_back(who2);
            edge[id2].push_back(who2);
        }
    }
    double low = max(A.z, B.z), high = 1e6;
    for(int i = 1; i <= 100; i++) {
        double mid = (low+high)/2;
        if(check(mid)) high = mid, ans = tmp;
        else low = mid;
    }
    printf("%d
", ans.size());
    for(int &t : ans) {
        printf("%d %d %d
", (int)(a[t].x+0.5), (int)(a[t].y+0.5), (int)(a[t].z+0.5));
    }
    return 0;
}

/*
*/