当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/21 18:14:51

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大佬说是逆序对，太强了。

平衡树卡过去非常勉强：

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

const int MAXN = 1e5 + 5;

int n;
ll q;

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

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

inline int NewNode(ll 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, ll 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);
    }
}

int GetRank(int id, ll v) {
    if(!id)
        return 0;
    else {
        if(v == val[id])
            return siz[ch[id][1]] + cnt[id];
        else if(v < val[id])
            return siz[ch[id][1]] + cnt[id] + GetRank(ch[id][0], v);
        else
            return GetRank(ch[id][1], v);
    }
}

const int INF = 1e9;

struct Point {
    int x, y;
    ll z;
    Point() {}
    Point(int x, int y): x(x), y(y) {}

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

} p[MAXN];

bool check(int k) {
    //printf("k=%d\n", k);
    Init();
    for(int i = 1; i <= n; ++i) {
        p[i].z = 1ll * p[i].y - 1ll * k * p[i].x;
        //printf("p[%d].z=%lld%c", i, p[i].z, " \n"[i == n]);
        //printf("p[%d].x=%d%c", i, p[i].x, " \n"[i == n]);
    }
    ll sum = 0;
    for(int i = 1, nxt; i <= n; i = nxt) {
        for(nxt = i + 1; nxt <= n && p[nxt].x == p[i].x; ++nxt);
        for(int j = i; j < nxt; ++j) {
            //int gr = GetRank(root, p[j].z);
            //printf("j=%d ,gr=%d\n", j, gr);
            sum += GetRank(root, p[j].z);
            //printf("sum=%lld\n", sum);
//            if(sum >= q)
//                return true;
        }
        for(int j = i; j < nxt; ++j)
            Insert(root, p[j].z);
    }
    if(sum >= q)
        return true;
    return false;
}

int solve() {
    scanf("%d%lld", &n, &q);
    int maxy = -INF, miny = INF;
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &p[i].x, &p[i].y);
        if(p[i].y > maxy)
            maxy = p[i].y;
        if(p[i].y < miny)
            miny = p[i].y;
    }
    sort(p + 1, p + 1 + n);
    /*for(int i = 1; i <= n; ++i) {
       //p[i].z = 1ll * p[i].y - 1ll * k * p[i].x;
       //printf("p[%d].z=%lld%c", i, p[i].z, " \n"[i == n]);
       printf("p[%d].x=%d%c", i, p[i].x, " \n"[i == n]);
    }*/
    int L = -(maxy - miny), R = 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--) {
            int res = solve();
            if(res >= INF)
                puts("INF");
            else
                printf("%d\n", res);
        }
    }
    return 0;
}

求逆序对，用树状数组的话，是这样思考：把其中一维离散化，用树状数组来表示，按另一维顺序插入。
下面是把z离散化，按x从小到大插入，那么每次合法的就是前面的比它小的x2里面z2>=z1的，这样就先求出<=z1-1的个数，然后用已经插入的数的个数i-1减去，这里要注意相同的x的处理，600ms：

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

const int MAXN = 1e5 + 5;

int n;
ll q;

int bit[MAXN];

inline void Init() {
    memset(bit, 0, sizeof(bit[0]) * (n + 1));
}

inline int Sum(int x) {
    int res = 0;
    while(x) {
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

inline void Add(int x, int v) {
    while(x <= n) {
        bit[x] += v;
        x += x & -x;
    }
}

struct Point {
    int x, y;
    ll z;
    Point() {}
    Point(int x, int y): x(x), y(y) {}
    bool operator<(const Point &p)const {
        return x < p.x;
    }
} p[MAXN];

ll pz[MAXN];

bool check(int k) {
    Init();
    for(int i = 1; i <= n; ++i)
        pz[i] = p[i].z = 1ll * p[i].y - 1ll * k * p[i].x;
    sort(pz + 1, pz + 1 + n);
    int pzn = unique(pz + 1, pz + 1 + n) - (pz + 1);
    for(int i = 1; i <= n; ++i)
        p[i].z = lower_bound(pz + 1, pz + 1 + pzn, p[i].z) - pz;
    ll sum = 0;
    for(int i = 1, nxt; i <= n; i = nxt) {
        for(nxt = i + 1; nxt <= n && p[nxt].x == p[i].x; ++nxt);
        for(int j = i; j < nxt; ++j) {
            sum += ((ll)i - 1) - Sum(p[j].z - 1);
            if(sum >= q)
                return true;
        }
        for(int j = i; j < nxt; ++j)
            Add(p[j].z, 1);
    }
    return false;
}

const int INF = 1e9;

int solve() {
    scanf("%d%lld", &n, &q);
    int maxy = -INF, miny = INF;
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &p[i].x, &p[i].y);
        if(p[i].y > maxy)
            maxy = p[i].y;
        if(p[i].y < miny)
            miny = p[i].y;
    }
    sort(p + 1, p + 1 + n);
    int L = -(maxy - miny), R = 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--) {
            int res = solve();
            if(res >= INF)
                puts("INF");
            else
                printf("%d\n", res);
        }
    }
    return 0;
}

离散化x的话，会更快，300ms，毕竟不用每次都对z进行一次unique然后lowerbound，的确少了一半的常数。

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

const int MAXN = 1e5 + 5;

int n;
ll q;

int bit[MAXN];

inline void Init() {
    memset(bit, 0, sizeof(bit[0]) * (n + 1));
}

inline int Sum(int x) {
    int res = 0;
    while(x) {
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

inline void Add(int x) {
    while(x <= n) {
        ++bit[x];
        x += x & -x;
    }
}

struct Point {
    int x, y, idx;
    ll z;
    Point() {}
    Point(int x, int y): x(x), y(y) {}
    bool operator<(const Point &p)const {
        return z == p.z ? idx<p.idx: z > p.z;
    }
} p[MAXN];

int px[MAXN], pxn;

bool check(int k) {
    Init();
    for(int i = 1; i <= n; ++i)
        p[i].z = p[i].y - 1ll * k * p[i].x;
    sort(p + 1, p + 1 + n);
    ll sum = 0;
    for(int i = 1; i <= n; ++i) {
        sum += Sum(p[i].idx - 1);
        if(sum >= q)
            return true;
        Add(p[i].idx);
    }
    return false;
}

const int INF = 1e9;

int solve() {
    scanf("%d%lld", &n, &q);
    int maxy = -INF, miny = INF;
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &p[i].x, &p[i].y);
        px[i] = p[i].x;
        if(p[i].y > maxy)
            maxy = p[i].y;
        if(p[i].y < miny)
            miny = p[i].y;
    }
    sort(px + 1, px + 1 + n);
    pxn = unique(px + 1, px + 1 + n) - (px + 1);
    for(int i = 1; i <= n; ++i)
        p[i].idx = lower_bound(px + 1, px + 1 + pxn, p[i].x) - px;
    int L = miny - maxy, R = 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--) {
            int res = solve();
            if(res >= INF)
                puts("INF");
            else
                printf("%d\n", res);
        }
    }
    return 0;
}

转载于:https://www.cnblogs.com/Yinku/p/11337258.html

相关文章：

  • 财务软件的设计
  • SCUT - 483 - 数轴上的点
  • ruby on rails开发B/S的相关经验
  • Codeforces - 1202D - Print a 1337-string... - 构造
  • 通用权限管理系统组件 (GPM - General Permissions Manager) 中实现大数据的高效分页显示...
  • 《学习之道》第十六章左脑的作用
  • Entity Framework 4.3尝试体会
  • 英汉《营销学》常用词汇-1
  • opencv源码解析之(2)：滤波前言2
  • 流媒体服务器搭建实例——可实现录音，录像功能
  • Redis之hash数据结构实现
  • SCUT - G - 魔法项链 - 树状数组
  • SCUT - 482 - 生成树上的点 - Prufer
  • ACM算法相关资料
  • 洛谷 - P1462 - 通往奥格瑞玛的道路 - 二分 - Dijkstra
  • “大数据应用场景”之隔壁老王（连载四）
  • Angular 响应式表单 基础例子
  • css布局，左右固定中间自适应实现
  • es6(二)：字符串的扩展
  • Java面向对象及其三大特征
  • Python代码面试必读 - Data Structures and Algorithms in Python
  • XML已死 ？
  • 二维平面内的碰撞检测【一】
  • 翻译 | 老司机带你秒懂内存管理 - 第一部（共三部）
  • 浮动相关
  • 官方解决所有 npm 全局安装权限问题
  • 官方新出的 Kotlin 扩展库 KTX，到底帮你干了什么？
  • 力扣(LeetCode)56
  • 实战｜智能家居行业移动应用性能分析
  • 小程序上传图片到七牛云（支持多张上传，预览，删除）
  • ​油烟净化器电源安全，保障健康餐饮生活
  • # 日期待t_最值得等的SUV奥迪Q9：空间比MPV还大，或搭4.0T，香
  • #[Composer学习笔记]Part1:安装composer并通过composer创建一个项目
  • #define与typedef区别
  • #mysql 8.0 踩坑日记
  • (02)Cartographer源码无死角解析-(03) 新数据运行与地图保存、加载地图启动仅定位模式
  • （20）目标检测算法之YOLOv5计算预选框、详解anchor计算
  • (C++)八皇后问题
  • (done) NLP “bag-of-words“ 方法 （带有二元分类和多元分类两个例子）词袋模型、BoW
  • （ISPRS，2023）深度语义-视觉对齐用于zero-shot遥感图像场景分类
  • （二）windows配置JDK环境
  • （附源码）springboot“微印象”在线打印预约系统 毕业设计 061642
  • （附源码）springboot掌上博客系统 毕业设计063131
  • （附源码）ssm基于web技术的医务志愿者管理系统 毕业设计 100910
  • （附源码）基于ssm的模具配件账单管理系统 毕业设计 081848
  • （附源码）基于SSM多源异构数据关联技术构建智能校园-计算机毕设 64366
  • (附源码)计算机毕业设计SSM保险客户管理系统
  • (一)appium-desktop定位元素原理
  • （转）iOS字体
  • （转）微软牛津计划介绍——屌爆了的自然数据处理解决方案(人脸/语音识别，计算机视觉与语言理解)...
  • .Net 4.0并行库实用性演练
  • .Net Core缓存组件(MemoryCache)源码解析
  • .NET delegate 委托 、 Event 事件
  • .net 提取注释生成API文档 帮助文档
  • .net 中viewstate的原理和使用