結果

問題 No.1144 Triangles
ユーザー semisagisemisagi
提出日時 2020-07-31 23:15:02
言語 Swift
(5.10.0)
結果
WA  
実行時間 -
コード長 5,026 bytes
コンパイル時間 12,973 ms
コンパイル使用メモリ 134,916 KB
実行使用メモリ 9,600 KB
最終ジャッジ日時 2024-07-06 21:22:38
合計ジャッジ時間 11,019 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
9,344 KB
testcase_01 AC 7 ms
9,344 KB
testcase_02 AC 7 ms
9,344 KB
testcase_03 AC 7 ms
9,344 KB
testcase_04 AC 696 ms
9,472 KB
testcase_05 AC 696 ms
9,472 KB
testcase_06 AC 737 ms
9,472 KB
testcase_07 AC 706 ms
9,472 KB
testcase_08 AC 728 ms
9,344 KB
testcase_09 AC 8 ms
9,216 KB
testcase_10 AC 8 ms
9,216 KB
testcase_11 AC 7 ms
9,344 KB
testcase_12 AC 7 ms
9,344 KB
testcase_13 AC 7 ms
9,344 KB
testcase_14 AC 648 ms
9,344 KB
testcase_15 AC 635 ms
9,344 KB
testcase_16 AC 695 ms
9,344 KB
testcase_17 AC 679 ms
9,344 KB
testcase_18 AC 679 ms
9,216 KB
testcase_19 AC 29 ms
9,344 KB
testcase_20 AC 8 ms
9,216 KB
testcase_21 AC 9 ms
9,600 KB
testcase_22 AC 647 ms
9,344 KB
testcase_23 AC 44 ms
9,472 KB
testcase_24 AC 628 ms
9,216 KB
testcase_25 AC 194 ms
9,344 KB
testcase_26 AC 26 ms
9,344 KB
testcase_27 AC 14 ms
9,344 KB
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

fileprivate struct Scanner {
    private var elements = [String]()
    private var index = 0
    
    mutating func peek() -> String {
        while elements.count == index {
            elements = readLine()!.split(separator: " ").map(String.init)
            index = 0
        }
        return elements[index]
    }
    
    mutating func next() -> String {
        let value = peek()
        index += 1
        return value
    }
    
    mutating func nextInt() -> Int {
        return Int(next())!
    }
    
    mutating func nextDouble() -> Double {
        return Double(next())!
    }
}

fileprivate let MOD = 1000000007

fileprivate struct Zn: Equatable {
    let n: Int
    
    init(_ n: Int) {
        self.n = n
    }
    
    static func + (lhs: Self, rhs: Self) -> Self {
        let n = lhs.n + rhs.n
        return Zn(n < MOD ? n : n - MOD)
    }
    
    static func - (lhs: Self, rhs: Self) -> Self {
        let n = lhs.n - rhs.n
        return Zn(n >= 0 ? n : n + MOD)
    }
    
    static func * (lhs: Self, rhs: Self) -> Self {
        Zn((lhs.n * rhs.n) % MOD)
    }
    
    static func += (lhs: inout Self, rhs: Self) {
        lhs = lhs + rhs
    }
    
    static func -= (lhs: inout Self, rhs: Self) {
        lhs = lhs - rhs
    }
    
    static func *= (lhs: inout Self, rhs: Self) {
        lhs = lhs * rhs
    }
    
    func pow(_ n: Int) -> Self {
        if n == 0 {
            return Zn(1)
        } else if n % 2 == 1 {
            return self * self.pow(n - 1)
        } else {
            return (self * self).pow(n / 2)
        }
    }
    
    var inverse: Self {
        self.pow(MOD - 2)
    }
    
    static func == (lhs: Self, rhs: Self) -> Bool {
        lhs.n == rhs.n
    }
}

fileprivate struct Complex: Comparable {
    var x: Int
    var y: Int
    
    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }
    
    static func + (lhs: Self, rhs: Self) -> Self {
        Self(lhs.x + rhs.x, lhs.y + rhs.y)
    }
    
    static func - (lhs: Self, rhs: Self) -> Self {
        Self(lhs.x - rhs.x, lhs.y - rhs.y)
    }
    
    static func * (lhs: Self, rhs: Self) -> Self {
        Self(lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x)
    }
    
    static func += (lhs: inout Self, rhs: Self) {
        lhs = lhs + rhs
    }
    
    static func -= (lhs: inout Self, rhs: Self) {
        lhs = lhs - rhs
    }
    
    static func *= (lhs: inout Self, rhs: Self) {
        lhs = lhs * rhs
    }
    
    static var zero: Self {
        Self(0, 0)
    }
    
    var norm: Int {
        x * x + y * y
    }
    
    var syougen: Int {
        if x > 0 && y >= 0 {
            return 0
        } else if x <= 0 && y > 0 {
            return 1
        } else if x < 0 && y <= 0 {
            return 2
        } else {
            return 3
        }
    }
    
    var conj: Complex {
        Complex(x, -y)
    }
    
    static func det(_ lhs: Complex, _ rhs: Complex) -> Int {
        lhs.x * rhs.y - lhs.y * rhs.x
    }
    
    static func < (lhs: Complex, rhs: Complex) -> Bool {
        if lhs == rhs {
            return false
        }
        if lhs == .zero {
            return true
        }
        if rhs == .zero {
            return false
        }
        if lhs.syougen != rhs.syougen {
            return lhs.syougen < rhs.syougen
        }
        if Self.det(lhs, rhs) != 0 {
            return Self.det(lhs, rhs) > 0
        }
        return lhs.norm < rhs.norm
    }
    
    static func == (lhs: Complex, rhs: Complex) -> Bool {
        lhs.x == rhs.x && lhs.y == rhs.y
    }
    
    func closewise(other: Complex) -> Bool {
        Self.det(self, other) >= 0
    }
}

fileprivate struct Array2D<Element> {
    let n1: Int
    let n2: Int
    private var elements: [Element]
    
    init(repeating: Element, _ n1: Int, _ n2: Int) {
        self.n1 = n1
        self.n2 = n2
        self.elements = [Element](repeating: repeating, count: n1 * n2)
    }
    
    subscript(i: Int, j: Int) -> Element {
        get {
            elements[i * n2 + j]
        }
        set {
            elements[i * n2 + j] = newValue
        }
    }
}


func main() {
    var scanner = Scanner()
    
    let N = scanner.nextInt()
    var P = [Complex]()
    for _ in 0 ..< N {
        let x = scanner.nextInt()
        let y = scanner.nextInt()
        P.append(Complex(x, y))
    }
    var answer = 0
    for k in 0 ..< N {
        let O = P[k]
        let Q = P.filter({ $0 != O }).map({ $0 - O }).sorted()
        var j = 0
        
        var sum = Complex.zero
        for i in 0 ..< Q.count {
            while j < i + Q.count, Q[i].closewise(other: Q[j % Q.count]) {
                sum += Q[j % Q.count]
                j += 1
            }
            sum.x %= MOD
            sum.y %= MOD
            answer += (Q[i].conj * sum).y
            answer %= MOD
            sum -= Q[i]
        }
    }
    answer *= Zn(3).inverse.n
    answer %= MOD
    if answer < 0 {
        answer += MOD
    }
    print(answer)
}

main()
0