hotpepsiの練習帳

SRM 641

21:07

Div1 Easy (250) TrianglesContainOrigin

問題

• 点の集合が与えられる
• 一直線上に3点が並ぶことはない
• 原点を内側に含む三角形が何個できるか求める

方針

• 任意の2点A,Bを選び、そこを底辺として、原点の向こう側にある点の範囲を数える
• 提出間に合わず
• 反時計回りに列挙できるように、2π足した点も配列に足しておく
• 角度がA＜B、かつ、(B-A)＜πの2点を底辺とする
• A＋πより大きくB＋π未満の点を数える
• 3辺のうち全ての2辺を列挙することになるので、最後に半分にする
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_641/TrianglesContainOrigin.cpp

結果

--- 0pts 232nd/519 rating 1312 -> 1298 (-14)

外積を使って解けるらしい。

http://togetter.com/li/756569