Codeforces 55 E. Very simple problem

問題

凸多角形および、点Pが与えられる。
凸多角形の頂点からなる三角形で、点Pを含むものはいくつあるか求めよ。

制約条件

多角形の角≦100000

方針

多角形の3点を結んでできる三角形から、Pを含まないような三角形の数を引く。

ある頂点iから見て、点Pを左側に見るような直線を引ける最も遠い頂点jを求めれば、
点Pを左手に見るような頂点iを頂点とする三角形の数は、
(j-i)*(j-i-1)/2個である。

これを尺取り法で、全てのiに対して求めれば、Pを含まない三角形が全て求まる。

点Pが凸多角形にそもそも含まれていない場合があるが、それはすぐに0を出力しておく。

ソースコード

double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}

void run(){
  int n,t;
  cin>>n;
  vector<P> p(2*n);
  rep(i,n)cin>>p[i].real()>>p[i].imag(), p[i+n]=p[i];
  cin>>t;
  while(t--){
    ll ans=n*(n-1ll)*(n-2)/6;
    P x; cin>>x.real()>>x.imag();
    int j=0;
    
    rep(i,n)if(cross(p[i+1]-p[i],x-p[i+1])>=0){
      cout<<0<<endl; goto END;
    }
    rep(i,n){
      j=max(j,i+1);
      while(j<2*n&&cross(p[j]-p[i],x-p[j])<0)j++;
      ans-=(j-i-1)*(j-i-2ll)/2;
    }
    cout<<ans<<endl; END:;
  }
}