pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Dynamic Convex Hull

CodeChef June Challenge 2016: Misha and Geometry

https://www.codechef.com/JUNE16/problems/MGCHGEOM 問題 以下の 2 種類のクエリが与えられる。 点(x, y) を追加する 点(x, y) を削除する クエリを順に処理し、処理するたびに凸包の面積を出力せよ。 クエリ数の合計は 105 以下

Educational Codeforces Round 13 F. Lena and Queries

http://codeforces.com/contest/678/problem/F 問題 以下の 3 種類のクエリを処理せよ。 点 (x,y) を set に追加する i 番目のクエリで追加した点を set から削除する xq+y の最大値を求める