SCUT - 484 - 平面上的点 - 数据结构

https://scut.online/p/484

一开始想的是按固定斜率的直线从无穷扫下来，但是一直都WA，不知道是哪里错了还是精度问题？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;

int dcmp(long double x, long double y) {
    if(fabs(x - y) <= 1e-14)
        return 0;
    return x < y ? -1 : 1;
}

int n;
ll q;

int ch[MAXN][2];
int val[MAXN];
int dat[MAXN], siz[MAXN], cnt[MAXN];
int tot, root;

inline void Init() {
    tot = 0;
    root = 0;
}

inline int NewNode(int v) {
    val[++tot] = v, dat[tot] = rand();
    ch[tot][0] = ch[tot][1] = 0;
    siz[tot] = 1, cnt[tot] = 1;
    return tot;
}

inline void PushUp(int id) {
    siz[id] = siz[ch[id][0]] + siz[ch[id][1]] + cnt[id];
}

inline void Rotate(int &id, int d) {
    int temp = ch[id][d ^ 1];
    ch[id][d ^ 1] = ch[temp][d];
    ch[temp][d] = id;
    id = temp;
    PushUp(ch[id][d]), PushUp(id);
}

inline void Insert(int &id, int v) {
    if(!id)
        id = NewNode(v);
    else {
        if(v == val[id])
            ++cnt[id];
        else {
            int d = v < val[id] ? 0 : 1;
            Insert(ch[id][d], v);
            if(dat[id] < dat[ch[id][d]])
                Rotate(id, d ^ 1);
        }
        PushUp(id);
    }
}

//找严格小于v的点的个数
int GetRank(int id, int v) {
    if(!id)
        return 0;
    else {
        if(v == val[id])
            return siz[ch[id][0]];
        else if(v < val[id])
            return GetRank(ch[id][0], v);
        else
            return siz[ch[id][0]] + cnt[id] + GetRank(ch[id][1], v);
    }
}

const ll INF = 1e9;

struct Point {
    long double x, y;
    Point() {}
    Point(long double x, long double y): x(x), y(y) {}

    Point Rotate(long double A) {
        return Point(x * cos(A) - y * sin(A), x * sin(A) + y * cos(A));
    }

    bool operator<(const Point &p)const {
        return (dcmp(x, p.x) != 0) ? (x < p.x) : (y < p.y);
    }


} p[MAXN], p2[MAXN];

int nxt[MAXN];

bool check(ll k) {
    Init();
    long double A = atan2(1.0, 1.0 * k);
    for(int i = 1; i <= n; ++i)
        p2[i] = p[i].Rotate(A);

    //按斜率排序
    sort(p2 + 1, p2 + 1 + n);

    for(int i = 1; i <= n; ++i) {
        p2[i] = p2[i].Rotate(-A);
        p2[i].x = round(p2[i].x);
        p2[i].y = round(p2[i].y);
    }

    ll sum = 0;
    for(int i = 1; i <= n; ++i) {
        int res = GetRank(root, (int)p2[i].x);;
        sum += res;
        if(sum >= q)
            return true;
        Insert(root, (int)p2[i].x);
    }
    return false;
}

ll CASE() {
    scanf("%d%lld", &n, &q);
    long double maxy = -INF, miny = INF;
    for(int i = 1; i <= n; ++i) {
        cin>>p[i].x>>p[i].y;
        //scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[i].y > maxy)
            maxy = p[i].y;
        if(p[i].y < miny)
            miny = p[i].y;
    }
    ll L = -round(maxy - miny), R = round(maxy - miny), M;
    while(1) {
        M = (L + R) >> 1;
        if(L == M) {
            if(check(L))
                return L;
            if(check(R))
                return R;
            return INF;
        }
        if(check(M))
            R = M;
        else
            L = M + 1;
    }
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int T;
    while(~scanf("%d", &T)) {
        while(T--) {
            ll res = CASE();
            if(res >= INF)
                puts("INF");
            else
                printf("%lld\n", res);
        }
    }
    return 0;
}

事实上枚举斜率之后对式子变形：

\(\frac{y_1-y_2}{x_1-x_2}<=k\)

不妨设x1>x2

\(y_1-y_2<=k(x_1-x_2)\)

即：

\(y_1-kx_1<=y_2-kx_2\)

即满足 \(x1>x2\) 且 \(y_1-kx_1<=y_2-kx_2\) 的数对的个数。lzf大佬说是逆序对，太强了。

SCUT - 484 - 平面上的点 - 数据结构

原文：https://www.cnblogs.com/Yinku/p/11337258.html