Problem:


	MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

カーテン

もうすぐ夏がやってくる．あなたは夏に向けて部屋の模様替えをすることにした．今年の夏はとても日差しが強いことが予想されており，まぶしいのが苦手なあなたには辛い季節になりそうだ．そこで，あなたは部屋の明るさを調節するために，部屋の窓にカーテンを取り付けようと考えた．

取り付けるカーテンは長方形であり，辺が地面に対して垂直，もしくは平行であるように取り付ける．また，あなたの部屋の窓は非常に特殊な形をしており，各辺が地面に平行または垂直であるような N 角形で表される．そのため，カーテンを取り付けたときにカーテンに覆われていない窓の面積がどのくらいになるのかを求めるのは難しい．部屋の明るさを調節するためにも，カーテンを取り付ける位置を決めた時にどのくらい窓が覆えるかを知ることは重要である．そこで，あなたは窓とカーテンの設置位置と形状が与えられたときに，カーテンに覆われていない窓の面積を求めるプログラムを作ることにした．

例として次のような窓とカーテンの設置の仕方を考える．この場合はカーテンに隠れていない窓の面積は 8 となる．この例はサンプル入力の 3 ケース目に対応する．

Input

入力は複数データセットからなる．
各データセットは次の形式で与えられる．

N
x1 y1
:
:
xN yN
a1 b1
a2 b2
a3 b3
a4 b4

最初の行には窓の持つ頂点数を表す整数 N が与えられる (4 ≤ N ≤ 100)．続く N 行には窓の相異なる頂点のx座標を表す整数 xi とy座標を表す整数 yi が与えられる (-20,000 ≤ xi, yi ≤ 20,000, 1 ≤ i ≤ N)．ここで，y軸の正の向きはx軸の正の向きから90度分反時計回りに回転させた方向とする．さらに，続く 4 行にはカーテンの相異なる頂点のx座標を表す整数 aj と y座標を表す整数 bj が与えられる (-20,000 ≤ aj, bj ≤ 20,000, 1 ≤ j ≤ 4)．窓，カーテンともに，それぞれの頂点は反時計回り順に与えられる．また，窓，カーテンを表す図形はそれぞれ自己交差がない図形である．

入力の終わりは1つの 0 からなる行で示す．

Output

各データセットについて，カーテンに覆われていない窓の面積を 1 行に出力せよ．ただし，面積は必ず整数値になることに注意せよ．

Sample Input

4
0 0
10 0
10 10
0 10
0 0
5 0
5 10
0 10
6
0 0
10 0
10 5
5 5
5 10
0 10
2 0
8 0
8 10
2 10
12
1 1
1 3
-1 3
-1 1
-3 1
-3 -1
-1 -1
-1 -3
1 -3
1 -1
3 -1
3 1
2 2
-2 2
-2 -2
2 -2
4
20000 20000
-20000 20000
-20000 -20000
20000 -20000
1000 1000
-1000 1000
-1000 -1000
1000 -1000
4
1000 1000
-1000 1000
-1000 -1000
1000 -1000
20000 20000
-20000 20000
-20000 -20000
20000 -20000
4
0 0
10 0
10 10
0 10
20 0
30 0
30 10
20 10
0

Output for Sample Input

50
30
8
1596000000
0
100



Sample input:
4
0 0
10 0
10 10
0 10
0 0
5 0
5 10
0 10
6
0 0
10 0
10 5
5 5
5 10
0 10
2 0
8 0
8 10
2 10
12
1 1
1 3
-1 3
-1 1
-3 1
-3 -1
-1 -1
-1 -3
1 -3
1 -1
3 -1
3 1
2 2
-2 2
-2 -2
2 -2
4
20000 20000
-20000 20000
-20000 -20000
20000 -20000
1000 1000
-1000 1000
-1000 -1000
1000 -1000
4
1000 1000
-1000 1000
-1000 -1000
1000 -1000
20000 20000
-20000 20000
-20000 -20000
20000 -20000
4
0 0
10 0
10 10
0 10
20 0
30 0
30 10
20 10
0


Sample output:
50
30
8
1596000000
0
100

Submission status: Accepted

Solution code:
from collections import defaultdict
INF = 10**9
while 1:
    N = int(input())
    if N == 0:
        break
    P = [list(map(int, input().split())) for i in range(N)]
    S = defaultdict(list)
    X = set()
    x0 = y0 = INF; x1 = y1 = -INF
    for i in range(4):
        x, y = map(int, input().split())
        x0 = min(x0, x); x1 = max(x1, x)
        y0 = min(y0, y); y1 = max(y1, y)
    S[y0] = [INF]; S[y1] = [INF]
    X.add(x0); X.add(x1)
    for x, y in P:
        S[y].append(x)
        X.add(x)
    xs = sorted(X)
    MP = {x: i for i, x in enumerate(xs)}
    L = len(xs)

    su = 0
    for i in range(N):
        xa, ya = P[i-1]
        xb, yb = P[i]
        su += xa*yb - ya*xb
    su = abs(su) // 2
    res = 0
    *ps, = S.items()
    ps.sort()
    mode = 0
    prv = -1
    U = [0]*L
    for y, vs in ps:
        if mode:
            px = 0; c = 0
            d = y - prv
            for i in range(L):
                if U[i]:
                    x = min(max(xs[i], x0), x1)
                    if c == 1:
                        res += d * (x - px)
                    c ^= 1
                    px = x
        for x in vs:
            if x == INF:
                mode ^= 1
            else:
                U[MP[x]] ^= 1
        prv = y
    print(su - res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

while True:
    N = input()
    if N == 0:
        break
    lst = []
    for i in range(N):
        x, y = map(int, raw_input().split())
        lst.append((x, y))
    x0, y0 = lst[0]
    x_pre, y_pre = lst[0]
    lst.append((x0, y0))
    sq_list = []
    for i in range(1, N):
        x, y = lst[i]
        if y != y_pre:
            flag = ((x > x0) ^ (y > y_pre))
            sq_list.append((min(x, x0),max(x, x0),min(y, y_pre),max(y, y_pre),flag))
        x_pre = x
        y_pre = y
    sq = []
    for i in range(4):
        x, y = map(int, raw_input().split())
        sq.append((x, y))
    sq.sort()
    sq = (sq[0][0], sq[3][0], sq[0][1], sq[3][1])
    ans = 0
    for s in sq_list:
        S = (s[1] - s[0]) * (s[3] - s[2])
        x1 = max(sq[0], s[0])
        x2 = min(sq[1], s[1])
        y1 = max(sq[2], s[2])
        y2 = min(sq[3], s[3])
        if y2 - y1 > 0 and x2 - x1 > 0:
            S -= (y2 - y1) * (x2 - x1)
        if s[4]:
            S *= -1
        ans += S
    print ans