9/22 PKU - Algorithmer’s note

数式だらけだから問題文見たほうが早い。

このままだと意味不明なので図示すると、一辺がX軸に重なり、互いに重なり合わない長方形がたくさん並んだ形になっている。Sの意味は、「その中で辺が軸に平行な最大の長方形の面積」。すると、2559とほとんど同じ問題だとわかる。あとは2559と同様に解くだけ。wi=0の場合に注意。

数列において、「長さ3の部分列を選び、それがその順に等差数列をなす」ようなものが存在するか否か判定せよ。

N<=10000でseveral test caseだから微妙に見えるが、O(N^2)で余裕みたい（偶奇を使ったりして若干高速化を入れたコードが16MSでACした）

円周上に何個か点があって、それらがいくつかの線で結ばれている。線は円の内部か外部かのみを通過する。１つの点からは高々１つの線しか出ない。線同士は交わらないという。本当か？

2つの線が違う側にないといけないか、というのはO(1)で判定できる。違う側にないといけない線たちをスリザーリンクの解法で使ったUnion Findを使ってseparateすると、矛盾が発生するか確認できる。