Codeforces Beta Round #13 D. Triangles

Codeforces

本番中に解けなかった問題シリーズ。今更ですが，前回のCodeforcesより。

問題

  • 平面上にN個の赤い点とM個の青い点があって，NもMも最大500。
  • 赤い点からなる三角形のうち，内部に青い点を含まないものの数は？
  • 制約として，どの3点も同一直線上にはない


解法

  • あまりに分からなかったのでEditorialを参考に実装。O(N^2(N+M))
  • 現在見ている辺との最小の偏角を持つ点の更新部分は，angleで角度計算をするとTLEでした
  • 外積を使った位置関係の比較にしたらAcceptに
  • ちなみに，コードはローカルでのテスト簡単化のため複数ケース対応で書いています。
#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>

using namespace std;

typedef complex<double> P;

double cross(P a, P b) { return imag(conj(a)*b); }
double angle(P a, P b) { return arg(conj(a)*b); }

int main(){
    int N, M;
    P pt[1000];
    while(cin >> N >> M){
        int ans = 0;
        double x, y;
        for(int i=0;i<N+M;i++) { cin >> x >> y; pt[i] = P(x,y); }
        for(int i=0;i<N;i++){
            vector< pair<double, int> > vp;
            for(int j=i+1;j<N+M;j++)
                vp.push_back(make_pair(angle(pt[i+1]-pt[i], pt[j]-pt[i]), j));
            sort(vp.begin(), vp.end());
            for(int j=0;j<vp.size();j++){
                int idx = vp[j].second;
                if(!(idx < N)) continue;
                int blueIdx = -1;
                for(int k=1;k<vp.size();k++){
                    int idx2 = vp[(j+k)%vp.size()].second;
                    if(cross(pt[idx2]-pt[idx], pt[i]-pt[idx]) < 0.0) break;
                    if(blueIdx == -1 || cross(pt[idx2]-pt[idx], pt[blueIdx]-pt[idx]) < 0.0){
                        if(idx2 < N) ans++;
                        else         blueIdx = idx2;
                    }
                }
            }
        }
        cout << ans << endl;
    }
}