2893번: XOR 도형

https://www.acmicpc.net/problem/2893

$O(2^n)$

x=a, y=b, x+y=c 로 이루어진 직각이등변삼각형을 (a,b,c)로 표현하자.

주어진 삼각형을 이루는 점들 집합을 ti라 하자.
구하고자 하는 구역
r=
sum(ti)
-2*sum(ti∩tj)
+4*sum(ti∩tj∩tk)
...

r구하기 위해 ti들을 교집합하는 연산을 구현해야 한다.
ti(ai,bi,ci)라고 하자.
ti∩tj를 잘 생각해보면 max(ai,aj)+max(bi,bj)<min(ci,cj) 인 경우 (max(ai,aj),max(bi,bj),min(ci,cj)) 인 직각이등변 삼각형이 됨을 알 수 있다.(위 부등식을 만족하지 않으면 ∅이다.)

∅이 아닌 경우만 따져서 계산하여 r을 구해주면 된다.

#include<cstdio>
int n, x[10], y[10], z[10];
double s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", x + i, y + i, z + i), z[i] += x[i] + y[i];
    for (int i = 1; i < 1 << n; i++) {
        int m = 1, a = 0, b = 0, c = 1e9;
        for (int j = 0; j<n; j++) if (i&(1 << j)) {
            m *= -2;
            if (a<x[j]) a = x[j];
            if (b<y[j]) b = y[j];
            if (c>z[j]) c = z[j];
        }
        s += (a + b < c) / -4.0*(c - a - b)*(c - a - b)*m;
    }
    printf("%.1lf", s);
    return 0;
}