Codeforces Round #208 (Div. 2) A. Dima and Continuous Line

,

問題文が難しかったのでinput/output等から察して書いた。

A. Dima and Continuous Line

問題

相異なる整数の列$x$が与えられる。 隣接する2項$x_i, x_{i+1}$のそれぞれに関して、線分$(x_i, 0), (x_{i+1}, 0)$を直径とする正円を描く。 このとき描いた線に交差は発生するか。

解法

隣接する2項の、全ての組に関して判定すればよい。$O(N^2)$。

実装

#!/usr/bin/env python3
n = int(input())
xs = list(map(int,input().split()))
found = False
for i in range(n-1):
    al = min(xs[i], xs[i+1])
    ar = max(xs[i], xs[i+1])
    for j in range(i):
        bl = min(xs[j], xs[j+1])
        br = max(xs[j], xs[j+1])
        if al < bl < ar < br or bl < al < br < ar:
            found = True
            break
    if found:
        break
print(found and 'yes' or 'no')