#1196618 (C#) No.622 点と三角柱の内外判定

• 問題: No.622 点と三角柱の内外判定
• ユーザー: 👑 kakel-san
• 提出日時: 2026-11-02 23:21:09
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,846 bytes
• コンパイル時間: 13,520 ms
• コンパイル使用メモリ: 171,684 KB
• 実行使用メモリ: 32,640 KB
• 最終ジャッジ日時: 2026-11-02 23:21:26
• 合計ジャッジ時間: 10,683 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
other	AC * 30 WA * 4

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (245 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static double[] NList => ReadLine().Split().Select(double.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var a = NList;
        var b = NList;
        var c = NList;
        var d = NList;
        WriteLine(Inner(a, b, c, d) ? "YES" : "NO");
    }
    static bool Inner(double[] a, double[] b, double[] c, double[] d)
    {
        var center = new double[3];
        var oa = new double[3];
        var ob = new double[3];
        for (var i = 0; i < 3; ++i)
        {
            oa[i] = b[i] - a[i];
            ob[i] = c[i] - a[i];
            center[i] = (a[i] + b[i] + c[i]) / 3;
        }
        var op = OuterProduct(oa, ob);
        {
            var div = Len(oa, new double[3]) * Len(ob, new double[3]);
            op = (op.ox / div, op.oy / div, op.oz / div);
        }
        var left = -2_000_000.0;
        var right = 2_000_000.0;
        while (right - left > 0.0000001)
        {
            var mid1 = (left * 2 + right) / 3;
            var mid2 = (left + right * 2) / 3;
            var a1 = new double[] { a[0] + op.ox * mid1, a[1] + op.oy * mid1, a[2] + op.oz * mid1 };
            var a2 = new double[] { a[0] + op.ox * mid2, a[1] + op.oy * mid2, a[2] + op.oz * mid2 };
            var len1 = Len(a1, d);
            var len2 = Len(a2, d);
            if (len1 < len2) right = mid2;
            else left = mid1;
        }
        var lr = (left + right) / 2;
        d[0] -= op.ox * lr;
        d[1] -= op.oy * lr;
        d[2] -= op.oz * lr;
        var xmin = Math.Min(a[0], Math.Min(b[0], c[0])) - 0.01;
        var xmax = Math.Max(a[0], Math.Max(b[0], c[0])) + 0.01;
        var ymin = Math.Min(a[1], Math.Min(b[1], c[1])) - 0.01;
        var ymax = Math.Max(a[1], Math.Max(b[1], c[1])) + 0.01;
        var zmin = Math.Min(a[2], Math.Min(b[2], c[2])) - 0.01;
        var zmax = Math.Max(a[2], Math.Max(b[2], c[2])) + 0.01;
        if (d[0] < xmin || xmax < d[0] || d[1] < ymin || ymax < d[1] || d[2] < zmin || zmax < d[2])
        {
            return false;
        }
        var abd = GetPrume(a, b, d);
        var rd = new double[3];
        for (var i = 0; i < 3; ++i) rd[i] = d[i] + 2 * abd[i];
        if (Len(d, c) > Len(rd, c)) return false;
        var bcd = GetPrume(b, c, d);
        for (var i = 0; i < 3; ++i) rd[i] = d[i] + 2 * bcd[i];
        if (Len(d, a) > Len(rd, a)) return false;
        var cad = GetPrume(c, a, d);
        for (var i = 0; i < 3; ++i) rd[i] = d[i] + 2 * cad[i];
        return Len(d, b) < Len(rd, b);
    }
    static (double ox, double oy, double oz) OuterProduct(double[] a, double[] b)
    {
        return (a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]);
    }
    static double Len(double[] a, double[] b)
    {
        return Math.Sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) + (a[2] - b[2]) * (a[2] - b[2]));
    }
    // 点Pから直線ABへの垂線ベクトルを求める
    static double[] GetPrume(double[] a, double[] b, double[] p)
    {
        var t = 0.0;
        if (a[0] != b[0]) t += (b[0] - a[0]) * (b[0] - 2 * p[0]) / (a[0] - b[0]) / (a[0] - b[0]);
        if (a[1] != b[1]) t += (b[1] - a[1]) * (b[1] - 2 * p[1]) / (a[1] - b[1]) / (a[1] - b[1]);
        if (a[2] != b[2]) t += (b[2] - a[2]) * (b[2] - 2 * p[2]) / (a[2] - b[2]) / (a[2] - b[2]);
        var ans = new double[3];
        ans[0] = t * (a[0] - b[0]) + b[0] - 2 * p[0];
        ans[1] = t * (a[1] - b[1]) + b[1] - 2 * p[1];
        ans[2] = t * (a[2] - b[2]) + b[2] - 2 * p[2];
        return ans;
    }
}