UVa 11020 Efficient Solutions

EfficientなSolutionを思いついたのでメモ．

条件を満たす点群（黒点）はこんな感じになる．各点を結んだ線分の左下か右上かを判定出来れば良い．
y=-xに各点を射影すると諸々の処理が簡単にできる．

新しい点Pを追加

y=-x上での両脇の点を結ぶ線分より左下ならPは必要，右上ならPは不要．
上図だと，青点が必要な点で，緑点が不要な点（矢印は両脇の点）．赤点は，両脇の点が同じ（内積が同じ）例．
左下・右下の判定は問題文の式のまま（両脇の点について判定式が満たされるか？）．
既に全く同じ点がある場合は単純にカウントアップする．マップで管理するのが楽．

新しい点Pによって消される点

Pの両脇から不要な点を可能な限り消していく．
青点の場合は，計3点が消える．

毎回の操作で消える点の数は入力次第だが，全体では|消える点|<=|追加する点|なので，時間計算量はO(NlogN)．