fork download
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <queue>
using namespace std;

#define in cin
#define out cout
#define X first
#define Y second

class BIT
{
private:
    int sz;
    vector<int> vec;

public:
    BIT(int n)
    {
        sz = 1; while(sz < n) sz *= 2;
        vec.resize(sz*2+1, 0);
    }

    void upd(int id)
    {
        id += sz-1;
        while(id)
        {
            vec[id]++;
            id /= 2;
        }
    }

    int get(int s, int e)
    {
        s += sz-1; e += sz-1;

        int ret = 0;
        while(s<=e)
        {
            if(s % 2 == 1) ret += vec[s];
            if(e % 2 == 0) ret += vec[e];
            s++; s /= 2;
            e--; e /= 2;
        }

        return ret;
    }
};

int main()
{
    int tc; in >> tc;
    while(tc--)
    {
        //input
        int n; double p, q; in >> n >> p >> q;
        vector< pair<double, double> > stars;
        for(int i=1; i<=n; i++)
        {
            double x, y; in >> x >> y;
            stars.push_back({x,y});
        }

        //tan
        vector< pair<double, int> > tan_p; //first for tan, second for id
        for(int i=1; i<=n; i++) {
            tan_p.push_back({atan2(stars[i-1].Y,stars[i-1].X-p), i});
        } sort(tan_p.begin(), tan_p.end());

        int P[111111];
        for(int i=1; i<=n; i++) P[i] = tan_p[i-1].Y;

        vector< pair<double, int> > tan_q;
        for(int i=1; i<=n; i++) {
            tan_q.push_back({atan2(stars[i-1].Y,stars[i-1].X-q), i});
        } sort(tan_q.begin(), tan_q.end());

        int Qt[111111];
        int Q[111111];
        for(int i=1; i<=n; i++) Qt[i] = tan_q[i-1].Y;
        for(int i=1; i<=n; i++) Q[Qt[i]] = i;

        BIT BIT_(n);
        long long res = 0;
        for(int i=1; i<=n; i++)
        {
            int t = Q[P[i]];
            int sum = BIT_.get(t, n); res += sum;
            BIT_.upd(t);
        }

        out << res << endl;
    }


    return 0;
}
Success #stdin #stdout 0s 4324KB
stdin
Standard input is empty
stdout
Standard output is empty