README.md

= How to invoke =

# Pass to verifier the input concatenated with your program's output
$ (cat in-hard1; python3 solve.py < in-hard1) | python3 verifier.py
Case #1: PASS. target=1.0, you=1.0, delta=0.0
Case #2: PASS. target=1.000001, you=1.0000009999999997, delta=2.220446049250313e-16
Case #3: PASS. target=1.000002, you=1.0000019999999998, delta=2.220446049250313e-16
Case #4: PASS. target=1.000003, you=1.0000029999999998, delta=2.220446049250313e-16
Case #5: PASS. target=1.000005, you=1.0000049999999998, delta=2.220446049250313e-16
Case #6: PASS. target=1.00001, you=1.0000099999999998, delta=2.220446049250313e-16
Case #7: PASS. target=1.414208, you=1.4142079999999997, delta=2.220446049250313e-16
Case #8: PASS. target=1.414209, you=1.4142089999999998, delta=2.220446049250313e-16
Case #9: PASS. target=1.41421, you=1.4142099999999997, delta=2.220446049250313e-16
Case #10: PASS. target=1.414211, you=1.4142109999999999, delta=2.220446049250313e-16
Case #11: PASS. target=1.414212, you=1.4142119999999998, delta=2.220446049250313e-16
Case #12: PASS. target=1.414213, you=1.4142129999999997, delta=2.220446049250313e-16
Case #13: PASS. target=1.414214, you=1.4142139999999994, delta=6.661338147750939e-16
Case #14: PASS. target=1.414215, you=1.4142149999999996, delta=4.440892098500626e-16
Case #15: PASS. target=1.414216, you=1.4142159999999997, delta=2.220446049250313e-16
Case #16: PASS. target=1.414217, you=1.4142169999999998, delta=2.220446049250313e-16
Case #17: PASS. target=1.414218, you=1.4142179999999998, delta=2.220446049250313e-16
Case #18: PASS. target=1.732034, you=1.7320339999999999, delta=2.220446049250313e-16
Case #19: PASS. target=1.732035, you=1.7320349999999998, delta=2.220446049250313e-16
Case #20: PASS. target=1.732036, you=1.7320359999999995, delta=4.440892098500626e-16
Case #21: PASS. target=1.732037, you=1.7320369999999996, delta=4.440892098500626e-16
Case #22: PASS. target=1.732038, you=1.7320379999999995, delta=4.440892098500626e-16
Case #23: PASS. target=1.732039, you=1.7320389999999999, delta=2.220446049250313e-16
Case #24: PASS. target=1.73204, you=1.7320399999999994, delta=6.661338147750939e-16
Case #25: PASS. target=1.732041, you=1.7320409999999997, delta=2.220446049250313e-16
Case #26: PASS. target=1.732042, you=1.7320419999999996, delta=4.440892098500626e-16
Case #27: PASS. target=1.732043, you=1.7320429999999993, delta=6.661338147750939e-16
Case #28: PASS. target=1.732044, you=1.7320439999999997, delta=2.220446049250313e-16
Case #29: PASS. target=1.732045, you=1.7320449999999996, delta=4.440892098500626e-16
Case #30: PASS. target=1.732046, you=1.7320459999999995, delta=4.440892098500626e-16
Case #31: PASS. target=1.732047, you=1.7320469999999994, delta=4.440892098500626e-16
Case #32: PASS. target=1.732048, you=1.7320479999999996, delta=4.440892098500626e-16
Case #33: PASS. target=1.732049, you=1.7320489999999995, delta=4.440892098500626e-16
Case #34: PASS. target=1.73205, you=1.7320499999999996, delta=4.440892098500626e-16
Case #35: PASS. target=1.014737, you=1.0147369999999998, delta=2.220446049250313e-16
Case #36: PASS. target=1.137363, you=1.1373629999999997, delta=2.220446049250313e-16
Case #37: PASS. target=1.166518, you=1.1665179999999997, delta=2.220446049250313e-16
Case #38: PASS. target=1.709334, you=1.7093339999999995, delta=4.440892098500626e-16
Case #39: PASS. target=1.109366, you=1.1093659999999999, delta=2.220446049250313e-16
Case #40: PASS. target=1.319114, you=1.3191139999999997, delta=2.220446049250313e-16
Case #41: PASS. target=1.385242, you=1.3852419999999999, delta=2.220446049250313e-16
Case #42: PASS. target=1.410717, you=1.4107169999999998, delta=2.220446049250313e-16
Case #43: PASS. target=1.303936, you=1.3039359999999998, delta=2.220446049250313e-16
Case #44: PASS. target=1.079978, you=1.0799779999999999, delta=2.220446049250313e-16
Case #45: PASS. target=1.039866, you=1.0398659999999997, delta=2.220446049250313e-16
Case #46: PASS. target=1.621015, you=1.6210149999999994, delta=6.661338147750939e-16
Case #47: PASS. target=1.624442, you=1.6244419999999997, delta=2.220446049250313e-16
Case #48: PASS. target=1.029838, you=1.0298379999999998, delta=2.220446049250313e-16
Case #49: PASS. target=1.517981, you=1.5179809999999996, delta=4.440892098500626e-16
Case #50: PASS. target=1.505026, you=1.5050259999999998, delta=2.220446049250313e-16

in-hard1.txt

50
1.000000
1.000001
1.000002
1.000003
1.000005
1.000010
1.414208
1.414209
1.414210
1.414211
1.414212
1.414213
1.414214
1.414215
1.414216
1.414217
1.414218
1.732034
1.732035
1.732036
1.732037
1.732038
1.732039
1.732040
1.732041
1.732042
1.732043
1.732044
1.732045
1.732046
1.732047
1.732048
1.732049
1.732050
1.014737
1.137363
1.166518
1.709334
1.109366
1.319114
1.385242
1.410717
1.303936
1.079978
1.039866
1.621015
1.624442
1.029838
1.517981
1.505026

verifier.py

#!/usr/bin/env python3

from math import atan2, sqrt
from itertools import product, combinations


class Point3:
    def __init__(self, x, y, z):
        self.x, self.y, self.z = x, y, z
    def __add__(self, other):
        return Point3(self.x + other.x, self.y + other.y, self.z + other.z)
    def __rmul__(self, other):
        return Point3(other * self.x, other * self.y, other * self.z)
    def __abs__(self):
        return sqrt(self.x ** 2 + self.y ** 2 + self.z ** 2)
    def cross(self, other):
        return Point3(
            self.y * other.z - self.z * other.y,
            self.z * other.x - self.x * other.z,
            self.x * other.y - self.y * other.x,
        )
    def to_2(self):
        return Point2(self.x, self.z)


class Point2:
    def __init__(self, x, y):
        self.x, self.y = x, y


def convex_area(points):
    def angle_key(p):
        return atan2(p.y, p.x)
    rv = -1
    for size in range(3, len(points)):
        for polygon in combinations(points, size):
            polygon = sorted(polygon, key=angle_key)
            area = 0
            for p, q in zip(polygon, polygon[1:] + polygon[:1]):
                area += p.x * q.y - p.y * q.x
            area = max(area, -area) / 2
            rv = max(rv, area)
    return rv


def aeq(a, b, tol=1e-6):
    return abs(a - b) < tol


# Receives input, then candidate output, concatenated
def main():
    case_count = int(input())
    targets = []
    for _ in range(case_count):
        target = float(input())
        targets.append(target)

    for case_number, target in enumerate(targets, start=1):
        header = input().strip()
        expected = 'Case #{}:'.format(case_number)
        if header != expected:
            raise ValueError('Unexpected header format: {!r}, expected={!r}'.format(header, expected))
        a = Point3(*map(float, input().split()))
        b = Point3(*map(float, input().split()))
        c = Point3(*map(float, input().split()))

        if not aeq(abs(a), 0.5) or not aeq(abs(b), 0.5) or not aeq(abs(c), 0.5):
            raise ValueError('Unexpected norm: {}, {}, {}, expected: 0.5'.format(abs(a), abs(b), abs(c)))
        if not abs(a.cross(b).cross(c)) < 1e-9:
            raise ValueError('Unexpected value of |a x b x c|: {}, expected near zero'.format(abs(a.cross(b).cross(c))))

        vertices = []
        for ma, mb, mc in product([-1, 1], repeat=3):
            vertices.append((ma * a + mb * b + mc * c).to_2())

        area_of_shadow = convex_area(vertices)
        delta = abs(target - area_of_shadow)
        result = 'PASS' if delta < 1e-6 else 'FAIL'
        print('Case #{}: {}. target={}, you={}, delta={}'.format(case_number, result, target, area_of_shadow, delta))


if __name__ == '__main__':
    main()