class Scanner { private var stack = [String]() private var index = 0 func peek() -> String { if stack.count == index { stack += readLine()!.split(separator: " ").map{ String($0) } } return stack[index] } func next() -> String { let value = peek() index += 1 return value } func nextInt() -> Int { return Int(next())! } func nextDouble() -> Double { return Double(next())! } } extension String { var characters: [Character] { self.map{ $0 } } } // 問題を象限ごとに分解する var scanner = Scanner() let N = scanner.nextInt() struct Point { let x: Int let y: Int } var A = [(x1: Int, y1: Int, x2: Int, y2: Int)]() for _ in 0 ..< N { let x1 = scanner.nextInt() let y1 = scanner.nextInt() let x2 = scanner.nextInt() let y2 = scanner.nextInt() A.append((x1: x1, y1: y1, x2: x2, y2: y2)) } struct MyDataStructure { var points = [Point(x: 0, y: 100000), Point(x: 100000, y: 0)] var area = 0 func dominate(_ p: Point, _ q: Point) -> Bool { p.x <= q.x && p.y <= q.y } mutating func remove(point p: Point) { main: while true { for i in 0 ..< points.count { if dominate(points[i], p) { area -= (points[i].x - points[i - 1].x) * (points[i].y - points[i + 1].y) points.remove(at: i) continue main } } break } } mutating func insert(point p: Point) { remove(point: p) var i = 0 while i < points.count { if points[i].x < p.x { i += 1 } else { break } } if !dominate(p, points[i]) { area += (p.x - points[i - 1].x) * (p.y - points[i].y) points.insert(p, at: i) } } } func count(points: [Point]) -> [Int] { var value = [Int]() var my = MyDataStructure() for point in points { let previousArea = my.area my.insert(point: point) value.append(my.area - previousArea) } return value } let answer = [ A.map{ a in Point(x: -a.x1, y: -a.y1) }, A.map{ a in Point(x: -a.x1, y: a.y2) }, A.map{ a in Point(x: a.x2, y: -a.y1) }, A.map{ a in Point(x: a.x2, y: a.y2) }].map(count) for i in 0 ..< N { var value = 0 for j in 0 ..< 4 { value += answer[j][i] } print(value) }