SRM 641 DIV1 Easy - TrianglesContainOrigin x

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084

・2次元の座標上の点が複数与えられる。
・このうち選んだ3点がなす三角形が原点を含む場合の数を求める。

解き方


まず3点を選んだ時に、その三角形が原点を含むかの判定をする必要がある。

これはatan2を使い、2点i,jを選んだときiのatan2+πとjのatan2+πの間に
もうひとつの点があれば原点を含む三角形となる。

次にこのような三角形の選び方は、N=2500のため
O(2500*2500*2500)では前探索できない。
ここで2点を選んだ時に残りの1点について2分探索を使うことで、
O(2500*2500*log2500)で計算量を間に合わせることができる。


コード


class TrianglesContainOrigin {

public: long long count(vector<int> x, vector<int> y) {
int n=x.size();
long long ret=0LL;
vector<double> p(n);

FORE(i,0,n)p[i]=atan2((double)x[i],(double)y[i]);
sort(all(p));

FORE(i,0,n)FORE(j,i+1,n)if(p[j]-p[i]<PI){
int e=lower_bound(p.begin(),p.end(),p[j]+PI)-p.begin();
int s=lower_bound(p.begin(),p.end(),p[i]+PI)-p.begin();
ret+=e-s;
}

return ret;
}

};

Share this

Related Posts

Previous
Next Post »