読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 033

abc033.contest.atcoder.jp

解説が詳しい
各点からすべての点への線分を考え角度を求める.
角度を求めた後, 鈍角と直角の数を数える.
ここでミソなのはx軸のx<0の半直線をまたぐ角度に対する対処(要するに特異点)でこれはすべての角度に2πを足して二分探索すればとける.

int main()
{
  ll n; cin >> n;
  ll a = 0, b = 0, c = 0;
  vector<P> T(n);
  REP(i,n) cin >> T[i].x >> T[i].y;
  REP(i,n)
  {
    vector<double> A;
    REP(j,n) if(j!=i) A.push_back((T[j]-T[i]).arg());
    REP(j,n-1) A.push_back(A[j]+2*M_PI);
    sort(A.begin(),A.end());
    REP(j,n-1)
    {
      int x = lower_bound(A.begin(),A.end(),A[j]+M_PI/2-EPS)-A.begin();
      int y = lower_bound(A.begin(),A.end(),A[j]+M_PI/2+EPS)-A.begin();
      int z = lower_bound(A.begin(),A.end(),A[j]+M_PI)-A.begin();
      b+=(y-x);
      c+=(z-y);
    }
  }
  a=n*(n-1)*(n-2)/6-(b+c);
  printf("%lld %lld %lld\n",a,b,c);
  return 0;
}