SRM 641 div1

easy
頂点を4つの象限で分類して（軸は適当に含める）考えると、原点を内部に含む三角形は次の二つのうちいずれかを満たすことに気づく。
(1)頂点が向かい合う二つの象限（または軸の上）にある
(2)頂点が三つの象限（または軸の上）にある

(1)について、ある象限の一つの頂点に注目して向かい合う象限の点に線分を引いたとき、y切片が正であるものの個数をu、負であるものの個数をvとすると、注目した頂点を含みかつ他の2頂点が向かい合う象限にある三角形の個数はuv個である。
これを各象限の各頂点について計算すると(1)を満たす三角形の個数が求まり、この計算量はO(n^2)

(2)について、向かい合う２つの象限の頂点の組による線分のy切片が正か負かで、残り一つの頂点がどの象限に属するかが決まる。またその象限の頂点ならどの頂点でも原点を含む三角形となるから、その象限に含まれる点の個数が「向かい合う２つの象限の頂点の組」に対する作りうる三角形の個数となる。
計算量はO(n^2)

(1)(2)をそれぞれ計算して和をとればよくて全体の計算量もO(n^2)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define IDX(v,a) distance(a.begin(),lower_bound(a.begin(),a.end(),v))
typedef long long ll;
typedef pair<int,int> P;

class TrianglesContainOrigin{
public:
	long long count(vector <int> x, vector <int> y){
        int n = x.size();
        long long ans = 0;
        vector<int> num[4];
        for(int i = 0; i < n; i++){
            if(x[i] >= 0 && y[i] > 0)
                num[0].push_back(i);
            if(x[i] > 0 && y[i] <= 0)
                num[1].push_back(i);
            if(x[i] <= 0 && y[i] < 0)
                num[2].push_back(i);
            if(x[i] < 0 && y[i] >= 0)
                num[3].push_back(i);
        }
        for(int k = 0; k < 4; k++){
            int l = (k+2)%4;
            for(int i = 0; i < num[k].size(); i++){
                int s = num[k][i];
                long long xs = x[s], ys = y[s];
                long long u=0, v=0;
                for(int j = 0; j < num[l].size(); j++){
                    int t = num[l][j];
                    long long xt = x[t], yt = y[t];
                    if((xs*yt-xt*ys) * (xs-xt) > 0){
                        u++;
                    }else{
                        v++;
                    }
                }
                ans += u*v;
            }
        }
        for(int i = 0; i < num[0].size(); i++){
            int s = num[0][i];
            long long xs = x[s], ys = y[s];
            for(int j = 0; j < num[2].size(); j++){
                int t = num[2][j];
                long long xt = x[t], yt = y[t];
                if((xs*yt-xt*ys) * (xs-xt) < 0){
                    ans += num[3].size();
                }else{
                    ans += num[1].size();
                }
            }
        }
        for(int i = 0; i < num[1].size(); i++){
            int s = num[1][i];
            long long xs = x[s], ys = y[s];
            for(int j = 0; j < num[3].size(); j++){
                int t = num[3][j];
                long long xt = x[t], yt = y[t];
                if((xs*yt-xt*ys) * (xs-xt) > 0){
                    ans += num[2].size();
                }else{
                    ans += num[0].size();
                }
            }
        }
        return ans;
	}
};