ABC 033 D - 三角形の分類 ( Geometry + Binary Search, EPS )

D: 三角形の分類 - AtCoder Beginner Contest 033 | AtCoder
This was quite interesting a problem, despite the meticulousness in double precision required.
First it is clear that it is impossible to simple enumerate each complete triangle, so we will probably imagine the solution to be something like enumerating up to two vertices, then maybe binary search on something else to top up the counts. If we first enumerate a vertex, then enumerate another vertex, they form a vector, we will realize that we can count the number of obtuse angles with binary search here. In other words, we will enumerate each vertex as the center, and then enumerate another vertex, forming the first vector, and finally binary search the leftmost and the rightmost vectors that also begins from the same center and the absolute difference of the angle formed by it and the first vector within 90, or 90. With these values and subtracting from total, we will be able to count the number of obtuse angles in total. The number of obtuse angle is exactly the number of obtuse triangles, and so is the number of right angles. At last, the number of acute triangles can be found with nC3 - obtuse_count - right_count.
I used atan2( det, dot ) to get the angle in radian, which returns in the range [ -PI, PI ], which was indeed very useful. To read more about this, one could look at this site.
Last but not least, EPS is required to produce the correct results, be especially careful.

const int MAXN = 2e3 + 3;
const int MAXABSXY = 1e4 + 2;
const double PI = acos( -1.0 );
 
int N;
int X[ MAXN ], Y[ MAXN ];
 
int nC3( int n ){
    return 1LL * ( n - 2 ) * ( n - 1 ) * n / 6;
}
 
const double EPS = 1e-9;
 
void solve(){
    cin >> N;
    for( int i = 0; i < N; ++i )
        cin >> X[ i ] >> Y[ i ];
 
    int obt_cnt = 0, right_cnt = 0;
    for( int i = 0; i < N; ++i ){
        vd ang;
        for( int j = 0; j < N; ++j ) if( i != j ){
            int a = X[ j ] - X[ i ], b = Y[ j ] - Y[ i ];
            double dot = a, det = b;
            double v = atan2( det, dot );
            if( v < 0 ) v += 2.0 * PI;
            ang.push_back( v );
            if( v <= PI / 2 ) ang.push_back( 2.0 * PI + v );
            if( v >= PI * 3 / 2 ) ang.push_back( v - 2.0 * PI );
        }
        sort( ang.begin(), ang.end() );
        for( int j = 0; j < ang.size(); ++j ) if( 0 <= ang[ j ] and ang[ j ] < 2.0 * PI ){
            int selb = -1, serb = -1; // smaller equal left / right bound
            int slb = -1, srb = -1; // strictly smaller left / right bound
            for( int lb = 0, rb = j; lb <= rb; ){ // careful that selb can become j
                int mid = lb + rb >> 1;
                if( fabs( ang[ mid ] - ang[ j ] ) <= PI / 2 + EPS )
                    selb = mid, rb = mid - 1;
                else
                    lb = mid + 1;
            }
            for( int lb = 0, rb = j; lb <= rb; ){
                int mid = lb + rb >> 1;
                if( fabs( ang[ mid ] - ang[ j ] ) < PI / 2 - EPS )
                    slb = mid, rb = mid - 1;
                else
                    lb = mid + 1;
            }
            for( int lb = j, rb = ang.size() - 1; lb <= rb; ){
                int mid = lb + rb >> 1;
                if( fabs( ang[ mid ] - ang[ j ] ) <= PI / 2 + EPS )
                    serb = mid, lb = mid + 1;
                else
                    rb = mid - 1;
            }
            for( int lb = j, rb = ang.size() - 1; lb <= rb; ){
                int mid = lb + rb >> 1;
                if( fabs( ang[ mid ] - ang[ j ] ) < PI / 2 - EPS )
                    srb = mid, lb = mid + 1;
                else
                    rb = mid - 1;
            }
            int cnt_se = serb - selb, cnt_s = srb - slb;
            int cnt_e = cnt_se - cnt_s;
            int cnt_o = N - 2 - cnt_se;
            right_cnt += cnt_e;
            obt_cnt += cnt_o;
        }
    }
 
    assert( right_cnt % 2 == 0 and obt_cnt % 2 == 0 ); // if this doesn't hold, something went wrong with precision
    right_cnt /= 2, obt_cnt /= 2;
    int acu_cnt = nC3( N ) - right_cnt - obt_cnt;
 
    cout << acu_cnt << " " << right_cnt << " " << obt_cnt << "\n";
}