TopCoder SRM 641 Div. 1 250 - TrianglesContainOrigin

Problem Statement:
SRM 641 Div. 1 250 - TrianglesContainOrigin

Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a \(O(N^2 \lg{N})\) running time complexity.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <cmath>
using namespace std;

double EPS = 1e-12;

double PI = 2*acos(0);
vector<double> angles;
int N;

int bsearch(double a) {
 int lo=0, hi = N-1, mid;
 while(lo <= hi) {
  mid = (lo+hi)/2;
  if(angles[mid] < a) {
   lo = mid +1;
  } else {
   hi = mid -1;
  }
 }
 return lo;
}

class TrianglesContainOrigin {
public:
 long long count(vector<int> x, vector<int> y) {
  N = x.size();
  angles.clear();
  for(int i=0;i<N;++i){
   if(x[i] == 0) {
    if(y[i] > 0) angles.push_back(PI/2.0);
    else angles.push_back(3.0 * PI / 2.0);
    continue;
   } else if (y[i] == 0) {
    if(x[i] > 0) angles.push_back(0);
    else angles.push_back(PI);
    continue;
   }
   double p = 1.0 * y[i] / x[i];
   double angle = atan(p);
   if(x[i] > 0 && y[i] > 0) {
    //first quadrant
   } else if(x[i] < 0 && y[i] > 0) {
    //second
    angle += PI;
   } else if(x[i] < 0 && y[i] < 0) {
    //third
    angle += PI;
   } else if(x[i] > 0 && y[i] < 0) {
    //fourth
    angle += 2*PI;
   } 
   angles.push_back(angle);
  }
  sort(angles.begin(), angles.end());
  long long ans = 0;
  //for(int i=0;i<N;++i)printf("\n%lf", angles[i]);
  for(int i=0;i<N;++i){
   for(int j=i+1;j<N;++j){
    if(angles[i] < PI) {
     if(angles[j] >= PI) {
      break;
     }
     double alpha = angles[i] + PI;
     double beta = angles[j] + PI;
     int L = bsearch(alpha);
     int R = bsearch(beta) - 1;
     //printf("\n%d %d", L, R);
     if(L>R)continue;
     ans += R - L + 1;
    } else {
     double alpha = angles[i] - PI;
     double beta = angles[j] - PI;
     int L = bsearch(alpha);
     int R = bsearch(beta) - 1;
     if(L>R) continue;
     ans += R - L + 1;
    }
   }
  }
  return ans;
 }
};