SRM 641 DIV1 Easy - TrianglesContainOrigin x
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084
・２次元の座標上の点が複数与えられる。
・このうち選んだ３点がなす三角形が原点を含む場合の数を求める。
解き方
まず３点を選んだ時に、その三角形が原点を含むかの判定をする必要がある。
これはatan2を使い、２点i,jを選んだときiのatan2+πとjのatan2＋πの間に
もうひとつの点があれば原点を含む三角形となる。
次にこのような三角形の選び方は、N=2500のため
O(2500*2500*2500）では前探索できない。
ここで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;
}
};
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;
}
};
