高精度模板
1 | define N 1e5 |
1 | define N 1e5 |
C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。
1 | set<int>::iterator it_set//一个set<int>类型的迭代器 |
1 | #include <iostream> |
题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的输入输出格式
输入格式:
第一行:n;2≤n≤200000接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000
首先考虑暴力,枚举所有点对,复杂度为O(N^2)
然后就是正解:
分治算法