Problem:
Problem I: Intersection of Two Prisms Suppose that P 1 is an infinite-height prism whose axis is parallel to the z -axis, and P 2 is also an infinite-height prism whose axis is parallel to the y -axis. P 1 is defined by the polygon C 1 which is the cross section of P 1 and the xy -plane, and P 2 is also defined by the polygon C 2 which is the cross section of P 2 and the x z-plane. Figure I.1 shows two cross sections which appear as the first dataset in the sample input, and
Figure I.2 shows the relationship between the prisms and their cross sections.   Figure I.1: Cross sections of Prisms   Figure I.2: Prisms and their cross sections   Figure I.3: Intersection of two prisms  Figure I.3 shows the intersection of two prisms in Figure I.2, namely, P 1 and P 2 . Write a program which calculates the volume of the intersection of two prisms. Input The input is a sequence of datasets. The number of datasets is less than 200. Each dataset is formatted as follows.  m n  x 11  y 11  x 12  y 12  . . .  x 1 m  y 1 m   x 21  z 21  x 22  z 22 . . .  x 2 n  z 2 n   m and n are integers (3 ≤ m ≤ 100, 3 ≤ n ≤ 100) which represent the numbers of the vertices of the polygons, C 1 and C 2 , respectively.  x 1 i , y 1 i , x 2 j and z 2 j are integers between -100 and 100, inclusive. ( x 1 i , y 1 i ) and ( x 2 j , z 2 j ) mean the i -th and j -th vertices' positions of C 1 and C 2 respectively. The sequences of these vertex positions are given in the counterclockwise order either on the xy -plane or the xz -plane as in Figure I.1. You may assume that all the polygons are convex , that is, all the interior angles of the polygons are less than 180 degrees. You may also assume that all the polygons are simple , that is, each polygon's boundary does not cross nor touch itself. The end of the input is indicated by a line containing two zeros. Output For each dataset, output the volume of the intersection of the two prisms, P 1 and P 2 , with a decimal representation in a line. None of the output values may have an error greater than 0.001. The output should not contain any other extra characters. Sample Input 4 3
7 2
3 3
0 2
3 1
4 2
0 1
8 1
4 4
30 2
30 12
2 12
2 2
15 2
30 8
13 14
2 8
8 5
13 5
21 7
21 9
18 15
11 15
6 10
6 8
8 5
10 12
5 9
15 6
20 10
18 12
3 3
5 5
10 3
10 10
20 8
10 15
10 8
4 4
-98 99
-99 -99
99 -98
99 97
-99 99
-98 -98
99 -99
96 99
0 0 Output for the Sample Input 4.708333333333333
1680.0000000000005
491.1500000000007
0.0
7600258.4847715655

Solution (Python):
def width(_X, _Y, _n, _x):
    lb = float("inf")
    ub = -float("inf")

    for j in range(0, _n):
        x1 = _X[j]
        y1 = _Y[j]
        x2 = _X[(j + 1) % _n]
        y2 = _Y[(j + 1) % _n]

        if (x1 - _x) * (x2 - _x) <= 0 and x1 != x2:
            y = y1 + (y2 - y1) * (_x - x1) / (x2 - x1)
            lb = min(lb, y)
            ub = max(ub, y)

    return max(0, ub - lb)


if __name__ == '__main__':
    while True:
        M, N = list(map(int, input().split()))
        if M == 0 and N == 0:
            break

        X1 = []
        Y1 = []
        X2 = []
        Z2 = []
        for i in range(M):
            tmp_x1, tmp_y1 = list(map(int, input().split()))
            X1.append(tmp_x1)
            Y1.append(tmp_y1)

        for i in range(N):
            tmp_x2, tmp_z2 = list(map(int, input().split()))
            X2.append(tmp_x2)
            Z2.append(tmp_z2)

        min1 = min(X1)
        max1 = max(X1)
        min2 = min(X2)
        max2 = max(X2)

        xs = X1 + X2
        xs = sorted(xs)
        res = 0
        for i in range(0, len(xs) - 1):
            a = xs[i]
            b = xs[i + 1]
            c = (a + b) / 2
            
            if min1 <= c <= max1 and min2 <= c <= max2:
                fa = width(X1, Y1, M, a) * width(X2, Z2, N, a)
                fb = width(X1, Y1, M, b) * width(X2, Z2, N, b)
                fc = width(X1, Y1, M, c) * width(X2, Z2, N, c)
                res += ((b - a) / 6) * (fa + 4 * fc + fb)
                

        print(res)

Solution (Python):

import sys
input = sys.stdin.readline



def width(X, Y, x):
    n = len(X)
    lb, ub = float('inf'), -float('inf')
    for i in range(n):
        x1, y1, x2, y2 = X[i], Y[i], X[(i+1) % n], Y[(i+1) % n]
        if (x1-x)*(x2-x) <= 0 and x1 != x2:
            y = y1 + (y2-y1) * (x-x1) / (x2-x1)
            lb = min(lb, y)
            ub = max(ub, y)
    return max(0, ub-lb)


while True:
    m, n = map(int, input().split())
    if m == n == 0:
        break
    X1 = [0] * m
    Y1 = [0] * m
    X2 = [0] * n
    Z2 = [0] * n
    for i in range(m):
        X1[i], Y1[i] = map(int, input().split())
    for i in range(n):
        X2[i], Z2[i] = map(int, input().split())
    min1, max1 = min(X1), max(X1)
    min2, max2 = min(X2), max(X2)
    X = X1 + X2
    X.sort()
    ans = 0
    for i in range(len(X)-1):
        a, b = X[i], X[i+1]
        c = (a+b) / 2
        if min1 <= c <= max1 and min2 <= c <= max2:
            fa = width(X1, Y1, a) * width(X2, Z2, a)
            fb = width(X1, Y1, b) * width(X2, Z2, b)
            fc = width(X1, Y1, c) * width(X2, Z2, c)
            ans += (b-a) / 6 * (fa+4*fc+fb)
    print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    M, N = map(int, readline().split())
    if M == N == 0:
        return False
    P = [list(map(int, readline().split())) for i in range(M)]
    Q = [list(map(int, readline().split())) for i in range(N)]
    xs = set()
    xs.update(x for x, y in P)
    xs.update(x for x, z in Q)
    *X, = xs
    X.sort()
    def calc(x):
        y_ma = -100; y_mi = 100
        for i in range(M):
            x0, y0 = P[i-1]; x1, y1 = P[i]
            if x0 <= x <= x1 or x1 <= x <= x0:
                if x0 == x1:
                    y_ma = max(y_ma, max(y1, y0))
                    y_mi = min(y_mi, min(y1, y0))
                else:
                    y = (x - x0)*(y1-y0) / (x1-x0) + y0
                    y_ma = max(y_ma, y)
                    y_mi = min(y_mi, y)
        if not y_mi <= y_ma:
            return 0
        z_ma = -100; z_mi = 100
        for i in range(N):
            x0, z0 = Q[i-1]; x1, z1 = Q[i]
            if x0 <= x <= x1 or x1 <= x <= x0:
                if x0 == x1:
                    z_ma = max(z_ma, max(z1, z0))
                    z_mi = min(z_mi, min(z1, z0))
                else:
                    z = (x - x0)*(z1-z0) / (x1-x0) + z0
                    z_ma = max(z_ma, z)
                    z_mi = min(z_mi, z)
        if not z_mi <= z_ma:
            return 0
        return (z_ma - z_mi) * (y_ma - y_mi)
    ans = 0
    L = len(X)
    for i in range(L-1):
        x0 = X[i]; x1 = X[i+1]
        s0 = calc(x0); s1 = calc((x0 + x1)/2); s2 = calc(x1)
        if s1 > 0:
            ans += (x1 - x0) * (s0 + s2 + 4*s1) / 6
    write("%.16f\n" % ans)
    return True
while solve():
    ...

Solution (Python):
def width(X,Y,x):
     n = len(X)
     lb,ub = float('inf'),-float('inf')
     for i in range(n):
          x1,y1,x2,y2 = X[i],Y[i],X[(i+1)%n],Y[(i+1)%n]
          if (x1-x)*(x2-x) <= 0 and x1 != x2:
               y = y1 + (y2-y1)*(x-x1)/(x2-x1)
               lb = min(lb,y)
               ub = max(ub,y)
     return max(0,ub-lb)

while 1:
     M,N = map(int,input().split())
     if not (M and N):
          break
     X1 = [0]*M
     Y1 = [0]*M
     X2 = [0]*N
     Z2 = [0]*N
     XS = [0]*N
     for i in range(M):
          X1[i],Y1[i] = map(int,input().split())
     for i in range(N):
          X2[i],Z2[i] = map(int,input().split())
     XS = X1+X2
     XS.sort()
     min1,max1 = min(X1),max(X1)
     min2,max2 = min(X2),max(X2)
     res = 0
     for i in range(len(XS)-1):
          a = XS[i]
          b = XS[i+1]
          c = (a+b)/2
          if min1 <= c <= max1 and min2 <= c <= max2:
               fa = width(X1,Y1,a)*width(X2,Z2,a)
               fb = width(X1,Y1,b)*width(X2,Z2,b)
               fc = width(X1,Y1,c)*width(X2,Z2,c)
               res += (b-a)/6 * (fa+4*fc+fb)
     print('%.10f'%res)

Solution (Python):

import sys
input = sys.stdin.readline



def width(X, Y, x):
    n = len(X)
    lb, ub = float('inf'), -float('inf')
    for i in range(n):
        x1, y1, x2, y2 = X[i], Y[i], X[(i+1) % n], Y[(i+1) % n]
        if (x1-x)*(x2-x) <= 0 and x1 != x2:
            y = y1 + (y2-y1) * (x-x1) / (x2-x1)
            lb = min(lb, y)
            ub = max(ub, y)
    return max(0, ub-lb)


while True:
    m, n = map(int, input().split())
    if m == n == 0:
        break
    X1 = [0] * m
    Y1 = [0] * m
    X2 = [0] * n
    Z2 = [0] * n
    for i in range(m):
        X1[i], Y1[i] = map(int, input().split())
    for i in range(n):
        X2[i], Z2[i] = map(int, input().split())
    min1, max1 = min(X1), max(X1)
    min2, max2 = min(X2), max(X2)
    X = X1 + X2
    X.sort()
    ans = 0
    for i in range(len(X)-1):
        a, b = X[i], X[i+1]
        c = (a+b) / 2
        if min1 <= c <= max1 and min2 <= c <= max2:
            fa = width(X1, Y1, a) * width(X2, Z2, a)
            fb = width(X1, Y1, b) * width(X2, Z2, b)
            fc = width(X1, Y1, c) * width(X2, Z2, c)
            ans += (b-a) / 6 * (fa+4*fc+fb)
    print(ans)