2/3

PKU 2330

奥の方から描いていくだけ。

PKU 2331

xについてDFSしてからyについてDFSする。

PKU 2333

点iと点jを結んだ時の面積は点iと点j-1を結んだ時の面積に三角形i,j,j-1の符号付面積を足せば求まるので、後はO(N²)通り全部試すだけ。L²がintに収まらないのに気付かず無駄にWAを重ねた。

PKU 2334

やるだけ。

PKU 2335

まず最初に3点を通る円を求めておく。これが正多角形の外接円になる。

この3点が正n角形の頂点になっているかどうかは、点1を頂点とする正n角形を実際に求めてみて、その点2と点3がその頂点になっているかどうか調べればよい。つまり O(n) で判定可能。

200角形以下と問題文に書いてあるので全部試す。

PKU 2336

dp_time[i] := 車iを向こう岸まで送って帰ってきた時の最短の時間

としてDP。dp_timeと同時に往復の回数も記録しておいてやればよい。

PKU 2337

アルファベットを頂点とするグラフを考えて、それの一筆書きを求めればよい。Fleuryのアルゴリズムを使う。

PKU 2338

やるだけ。

PKU 2339

やるだけ。

PKU 2689

ミラー-ラビンでTLEったので篩に書き換えた。見事にPEをもらったので書き直してAC。