2020/2/24

SWERC 2019 F

単純多角形の面積

頂点の順番がわかっているので、適当な点を定めて、隣り合う頂点のpairとの三角形をそれぞれ考えて、符号付きの三角形の面積を足し合わせればよい

偏角の向きを見て符号を決定していた→外積でいいね(偏角の向きを見るのも結局外積

 

Codeforces 1311 D

3つある→真ん中で全探索

 

約数を前計算しておいて、cとその約数を全探索する方が実装は楽

約数個数関数のオーダーについて:

https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/

https://codeforces.com/blog/entry/651

http://oeis.org/search?q=1344+maximal+divisors

最悪ケースがおよそ立方根の大きさになる

 

Codeforces 1311 F

数え上げ

相対速度が問題になるので速度を全て正にして考える

各点に対して、

座標も速度も小さい点と、座標も速度も大きい点の個数と距離を求めればよい

→点を座標の昇順に走査しながら、今見ている左側、右側それぞれにある速度ごとの点の座標をBITで管理し、適宜計算していけばよい

 

 

計算量の余裕を見て適宜楽な方針でやる意識を