// ref: https://stackoverflow.com/a/14382692
public class TriangleInt {
	private final int z20, x02, z01, x10;
	private final long x2z0_x0z2, x0z1_x1z0, area;
	private final double det;

	public TriangleInt(int x0, int z0, int x1, int z1, int x2, int z2) {
		long a = (long)x0 * (z1 - z2) + (long)z0 * (x2 - x1) + (long)x1 * z2 - (long)z1 * x2;
		if (a < 0) { // counter-clockwise
			int t = x1;
			x1 = x2;
			x2 = t;
			t = z1;
			z1 = z2;
			z2 = t;
			a = -a;
		}
		z20 = z2 - z0;
		x02 = x0 - x2;
		z01 = z0 - z1;
		x10 = x1 - x0;
		x2z0_x0z2 = (long)x2 * z0 - (long)x0 * z2;
		x0z1_x1z0 = (long)x0 * z1 - (long)x1 * z0;
		area = a;
		det = 1.0 / ((long)x10 * z20 - (long)x02 * z01);
	}

	public boolean isPointIn(int x, int z) {
		long s = z20 * (long)x + x02 * (long)z + x2z0_x0z2;
		if (s <= 0)
			return false;
		long t = z01 * (long)x + x10 * (long)z + x0z1_x1z0;
		if (t <= 0)
			return false;
		return s + t < area;
	}

	public int calcY(int x0, int y0, int z0, int y1, int y2, int x, int z) {
		double ld1 = (z20 * ((long)x - x0) + x02 * ((long)z - z0)) * det;
		double ld2 = (z01 * ((long)x - x0) + x10 * ((long)z - z0)) * det;
		return (int)(ld1 * y1 + ld2 * y2 + (1 - ld1 - ld2) * y0);
	}

	public static int[] calcClosestPoint(int x0, int y0, int z0, int x1, int y1, int z1, int x2, int y2, int z2,
										 int x, int y, int z) {
		// Check if p is in vertex region outside A
		int x01 = x1 - x0;
		int y01 = y1 - y0;
		int z01 = z1 - z0;
		int x02 = x2 - x0;
		int y02 = y2 - y0;
		int z02 = z2 - z0;
		int x0x = x - x0;
		int y0x = y - y0;
		int z0x = z - z0;

		long d1 = (long)x01 * x0x + (long)y01 * y0x + (long)z01 * z0x;
		long d2 = (long)x02 * x0x + (long)y02 * y0x + (long)z02 * z0x;

		// Barycentric coordinates (1,0,0)
		if (d1 <= 0 && d2 <= 0)
			return new int[]{x0, y0, z0};

		// Check if p is in vertex region outside B
		int x1x = x - x1;
		int y1x = y - y1;
		int z1x = z - z1;
		long d3 = (long)x01 * x1x + (long)y01 * y1x + (long)z01 * z1x;
		long d4 = (long)x02 * x1x + (long)y02 * y1x + (long)z02 * z1x;

		// Barycentric coordinates (0,1,0)
		if (d3 >= 0 && d4 <= d3)
			return new int[]{x1, y1, z1};

		// Check if p is in edge region outside AB, if so return a projection of p onto AB
		long vc = d1 * d4 - d3 * d2;
		if (d1 >= 0 && d3 <= 0 && vc <= 0) {
			// Barycentric coordinates (1-v, v, 0)
			double v = (double)d1 / (d1 - d3);
			return new int[]{
					x0 + (int)(x01 * v),
					y0 + (int)(y01 * v),
					z0 + (int)(z01 * v),
			};
		}

		// Check if p is in vertex region outside C
		int x2x = x - x2;
		int y2x = y - y2;
		int z2x = z - z2;
		long d5 = (long)x01 * x2x + (long)y01 * y2x + (long)z01 * z2x;
		long d6 = (long)x02 * x2x + (long)y02 * y2x + (long)z02 * z2x;

		// Barycentric coordinates (0,0,1)
		if (d6 >= 0 && d5 <= d6)
			return new int[]{x2, y2, z2};

		// Check if p is in edge region of AC, if so return a projection of p onto AC
		long vb = d5 * d2 - d1 * d6;
		if (d2 >= 0 && d6 <= 0 && vb <= 0) {
			// Barycentric coordinates (1-v, 0, v)
			double v = (double)d2 / (d2 - d6);
			return new int[]{
					x0 + (int)(x02 * v),
					y0 + (int)(y02 * v),
					z0 + (int)(z02 * v),
			};
		}

		// Check if p is in edge region of BC, if so return projection of p onto BC
		long va = d3 * d6 - d5 * d4;
		long d43 = d4 - d3;
		long d56 = d5 - d6;
		if (d43 >= 0 && d56 >= 0 && va <= 0) {
			double v = (double)d43 / (d43 + d56);
			return new int[]{
					x1 + (int)((x2 - x1) * v),
					y1 + (int)((y2 - y1) * v),
					z1 + (int)((z2 - z1) * v),
			};
		}
		// P is inside the face region. Compute the point using its barycentric coordinates (u, v, w)
		double denom = 1.0 / (va + vb + vc);
		double v = vb * denom;
		double w = vc * denom;

		// This is equal to: u*a + v*b + w*c, u = va*denom = 1 - v - w;
		return new int[]{
				x0 + (int)(x01 * v + x02 * w),
				y0 + (int)(y01 * v + y02 * w),
				z0 + (int)(z01 * v + z02 * w),
		};
	}

	public static void main(String[] args) {
		int x0 = -6, z0 = 10;
		int x1 = 13, z1 = -3;
		int x2 = -10, z2 = -15;
		var t1 = new TriangleInt(x0, z0, x1, z1, x2, z2);
		var t2 = new TriangleInt(x0, z0, x2, z2, x1, z1);
		System.out.println("---------------------------------");
		for (int z = 16; z >= -16; z--) {
			for (int x = -16; x <= 16; x++) {
				System.out.print(t1.isPointIn(x, z) ? '*' : ' ');
				if (t1.isPointIn(x, z) != t2.isPointIn(x, z))
					throw new AssertionError();
			}
			System.out.println();
		}
		System.out.println("---------------------------------");
	}
}