2018-07-03から1日間の記事一覧

AOJ1132 : Circle and Points

最適解が2点以上含む場合は、そのうちの2点を通る円でその最適解を必ず構成できる。 最適解を構成する頂点の集合をSとする。(|S|>=2)。Sの外側の点だけを拾って凸包を構成する。ただし、Sの点が一直線上に並ぶ場合は線分を構成する。これをTとおく。Sの点を…

Marked Ancestor (AOJ 2170, JAG Summer 2009)

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。 vector<vi> G(N); FOR(i, 1, N) { int p; cin >> p; --p; G[p].push_back(i); } HLDecomposition hld(G); // 0ならばマークされていない。 // そうでな</vi>…