热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

平面中有若干个点,寻找距离最近的两个点,输出其编号

代码:1#include<iostream>2#include<vector>3#include<algorithm

代码:

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 using namespace std;
  8 
  9 struct Point
 10 {
 11     double m_x, m_y;
 12     Point():m_x(0.0),m_y(0.0) {}
 13     Point(double x, double y):m_x(x),m_y(y) {}
 14     bool operator==(const Point& p) const
 15     {
 16         return m_x==p.m_x && m_y==p.m_y;
 17     }
 18 };
 19 
 20 ostream& operator<<(ostream& os, const Point& p)
 21 {
 22     return os <<"(" <"," <")";
 23 }
 24 template<class T, class Pr>
 25 void insert_sort(vector &vec, int l, int r, Pr pred)
 26 {
 27     int i, j;
 28     for (i=l+1; i<=r; i++)
 29     {
 30         T tmp = vec[i];
 31         for (j=i-1; j>=l && pred(tmp,vec[j]); j--)
 32             vec[j+1]=vec[j];
 33         vec[j+1] = tmp;
 34     }
 35 }
 36 template<class T>
 37 int get_position(vector &vec, int l, int r, T key)
 38 {
 39     for (int i=l; i<=r; i++)
 40         if (key == vec[i])
 41             return i;
 42     return -1;
 43 }
 44 template<class T, class Pr>
 45 int partition(vector &vec, int l, int r, Pr pred)
 46 {
 47     int i, j;
 48     for (i=l+1,j=l; i<=r; i++)
 49     {
 50         if (pred(vec[i],vec[l]))
 51         {
 52             ++j;
 53             swap(vec[i],vec[j]);
 54         }
 55     }
 56     swap(vec[j],vec[l]);
 57     return j;
 58 }
 59 
 60 template<class T, class Pr>
 61 T select(vector &vec, int l, int r, int k, Pr pred)
 62 {
 63     int n = r-l+1;
 64     if (n==1)
 65     {
 66         if (k!=0)
 67             printf("Out of Boundary!\n");
 68         return vec[l];
 69     }
 70     int cnt = n/5;
 71     int tcnt = (n+4)/5;
 72     int rem = n%5;
 73     vector group(tcnt);
 74     int i, j;
 75     for (i=0,j=l; i5)
 76     {
 77         insert_sort(vec, j, j+4, pred);
 78         group[i] = vec[j+2];
 79     }
 80     if (rem)
 81     {
 82         insert_sort(vec, j, j+rem-1, pred);
 83         group[i] = vec[j+(rem-1)/2];
 84     }
 85     T key = select(group, 0, tcnt-1, (tcnt-1)/2, pred);
 86 
 87     int key_pos = get_position(vec, l, r, key);
 88     swap(vec[key_pos], vec[l]);
 89     int pos = partition(vec, l, r, pred);
 90     int x = pos - l;
 91     if (x == k) return key;
 92     else if (x < k)
 93         return select(vec, pos+1, r, k-x-1, pred);
 94     else
 95         return select(vec, l, pos-1, k, pred);
 96 }
 97 double dist(const Point& a, const Point& b)
 98 {
 99     double x = a.m_x-b.m_x;
100     double y = a.m_y-b.m_y;
101     return sqrt(x*x+y*y);
102 }
103 
104 bool cmpX(const Point& a, const Point& b)
105 {
106     return a.m_x < b.m_x;
107 }
108 
109 bool cmpY(const Point& a, const Point& b)
110 {
111     return a.m_y < b.m_y;
112 }
113 
114 double minDifferent(vector p, int l, int r, vector &result)
115 {
116     if ((r-l+1)==2)
117     {
118         result[0] = p[l];
119         result[1] = p[r];
120         if (cmpX(p[r],p[l])) swap(p[l], p[r]);
121         return dist(p[l], p[r]);
122     }
123     if ((r-l+1)==3)
124     {
125         insert_sort(p, l, r, cmpX);
126         double tmp1 = dist(p[l], p[l+1]);
127         double tmp2 = dist(p[l+1], p[l+2]);
128         double ret = min(tmp1, tmp2);
129         if (tmp1 == ret)
130         {
131             result[0] = p[l];
132             result[1] = p[l+1];
133         }
134         else
135         {
136             result[0] = p[l+1];
137             result[1] = p[l+2];
138         }
139         return ret;
140     }
141     int mid = (r+l)>>1;
142     Point median = select(p, l, r, mid-l, cmpX);
143     vector res1(2), res2(2);
144     double min_l = minDifferent(p, l, mid, res1);
145     double min_r = minDifferent(p, mid+1, r, res2);
146     double minum = min(min_l, min_r);
147     if (minum == min_l)
148     {
149         result[0] = res1[0];
150         result[1] = res1[1];
151     }
152     else
153     {
154         result[0] = res2[0];
155         result[1] = res2[1];
156     }
157     vector yvec;
158     int i, j;
159     for (i=mid+1; i<=r; i++)
160         if (p[i].m_x - p[mid].m_x < minum)
161             yvec.push_back(Point(p[i]));
162     for (i=mid; i>=l; i--)
163         if (p[mid+1].m_x - p[i].m_x < minum)
164             yvec.push_back(Point(p[i]));
165     sort(yvec.begin(), yvec.end(), cmpY);
166     for (i=0; i)
167     {
168         for (j=i+1; j169                 j<=i+7; j++)
170         {
171             double delta = dist(yvec[i],yvec[j]);
172             if (delta < minum)
173             {
174                 minum = delta;
175                 result[0] = yvec[i];
176                 result[1] = yvec[j];
177             }
178         }
179     }
180     return minum;
181 }
182 
183 int main()
184 {
185     int n, i, j;
186     double x, y;
187     int k = 0;
188     map<int,Point> m;
189     vector result(2);
190     vector input;
191     cin >> n;
192     for (i=0; i)
193     {
194         cin >> x;
195         cin >> y;
196         input.push_back(Point(x,y));
197         m.insert(pair<int,Point>(k,Point(x,y)));
198         k++;
199     }
200     double minum = minDifferent(input, 0, input.size()-1, result);
201 
202     for(map<int,Point>::iterator it = m.begin();it != m.end();it++)
203     {
204         if(it->secOnd== result[0])
205         {
206             cout<first;
207         }
208         if(it->secOnd== result[1])
209         {
210             cout<<" "<first;
211         }
212     }
213 
214 
215     return 0;
216 }
View Code

 


推荐阅读
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • ImmutableX Poised to Pioneer Web3 Gaming Revolution
    ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]
author-avatar
漫步乡间2012
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有