HDU 4631 set维护

简介:

题意:给出n有n个点,每次插入计算最小点对距离,然后把距离和求出来。

用multiset按x坐标大小维护就行了。14s 

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
struct point
{
    long long x,y;
    bool operator < (const point &m) const
    {
        if(x==m.x)
            return y<m.y;
        return x<m.x;
    }
};
multiset<point> myset;
multiset<point>::iterator it,i1,i2;
long long dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long getmin(long long m,point a)
{
    long long ans=m;
    it=myset.lower_bound(a);
    for(i1=it; i1!=myset.end(); i1++)
    {
        long long dx=a.x-i1->x;
        if(dx*dx>=ans)
            break;
        long long dy=a.y-i1->y;
        ans=min(ans,dx*dx+dy*dy);
    }
    for(i1=it; i1!=myset.begin();)
    {
        i1--;
        long long dx=a.x-i1->x;
        if(dx*dx>=ans) break;
        long long dy=a.y-i1->y;
        ans=min(ans,dx*dx+dy*dy);
    }
    myset.insert(a);
    return ans;
}
int main()
{
    int t,n;
    long long ax,ay,bx,by,cx,cy,ans,m;
    scanf("%d",&t);
    while(t--)
    {
        myset.clear();
        scanf("%d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&ax,&bx,&cx,&ay,&by,&cy);
        point a;
        a.x=bx%cx,a.y=by%cy,ans=0;
        m=1e18;
        myset.insert(a);
        for(int i=1; i<n; i++)
        {
            a.x=(a.x*ax+bx)%cx,a.y=(a.y*ay+by)%cy;
            m=getmin(m,a);
            ans+=m;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}



目录
相关文章
hdu 1558 Segment set
点击打开hdu 1558 思路: 计算几何+并查集 分析: 1 有n个操作,最后求有几个集合或者说是连通分量 2 对于输入一条线段我们就去前面找能够和它相交的线段,利用并查集进行合并并且更新rank数组,rank[x]数组保存的是以x为跟...
805 0
Set和Map有什么区别?
Set和Map有什么区别?
117 1
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
123 2
for...of循环在遍历Set和Map时的注意事项有哪些?
for...of循环在遍历Set和Map时的注意事项有哪些?
63 0
|
1月前
|
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器,其允许通过键值快速的索引到对应的元素。在unordered_set中,元素的值同时也是唯一地标识它的key。在内部,unordered_set中的元素没有按照任何特定的顺序排序,为了能在常数范围内找到指定的key,unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快,但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
99 0
用一棵红黑树同时封装出map和set
再完成上面的代码后,我们的底层代码已经完成了,这时候已经是一个底层STL的红黑树了,已经已符合库里面的要求了,这时候我们是需要给他穿上对应的“衣服”,比如穿上set的“衣服”,那么这个穿上set的“衣服”,那么他就符合库里面set的要求了,同样map一样,这时候我们就需要实现set与map了。因此,上层容器map需要向底层红黑树提供一个仿函数,用于获取T当中的键值Key,这样一来,当底层红黑树当中需要比较两个结点的键值时,就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
35 0
set、map、multiset、multimap的介绍及使用以及区别,注意事项
set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列。set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重。set默认是升序的,但是其内部默认不是按照大于比较,而是按照小于比较。set中的元素不能被修改,因为set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树。
94 0
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问