YRZ001030 @ 2020-02-19 22:42:57
#include"stdio.h"
#include"string.h"
#include"vector"
#include"math.h"
#include"algorithm"
using namespace std;
typedef struct Node{
double x,y;
int id;
}Node;
int n;
Node node[200100];
Node tran[200100];
double minx = 2001020202;
int cmpx(Node a,Node b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int cmpy(Node a,Node b){
return a.y < b.y;
}
void dist_minx(Node a,Node b){
double sum = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
minx = min(minx,sum);
}
void merge_node(int l,int mid,int r)
{
int t = 0;
int i = l,j = mid + 1;
while(i <= mid && j <= r)
{
if(node[i].y < node[j].y)
{
tran[++ t] = node[i]; i ++; continue;
} else {
tran[++ t] = node[j]; j ++; continue;
}
}
while(i <= mid) tran[++ t] = node[i];
while(j <= r) tran[++ t] = node[j];
for(int i = l; i <= r; i ++)
node[i] = tran[i - l + 1];
}
void Blocking(int l,int r)
{
if(r - l <= 3)
{
for(int i = l; i < r; i ++)
{
for(int j = i + 1; j < r; j ++)
{
dist_minx(node[i],node[j]);
}
}
sort(node + l,node + r + 1,cmpy);
return ;
}
int mid = (l + r) >> 1;
double midx = node[mid].x;
Blocking(l,mid); Blocking(mid + 1,r);
merge_node(l,mid,r);
vector<Node> Q;
for(int i = l; i <= r; i ++)
{
if(fabs(node[i].x - midx) >= minx) continue;
for(int j = Q.size(); j >= 0; j --)
{
if(fabs(Q[j].y - node[i].y) >= minx) break;
dist_minx(Q[j],node[i]);
}
Q.push_back(node[i]);
}
return ;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
{
scanf("%lf%lf",&node[i].x,&node[i].y);
node[i].id = i;
}
sort(node + 1,node + n + 1,cmpx);
Blocking(1,n);
printf("%0.4lf\n",minx);
}
哭了 一片re 本地却可以
by syksykCCC @ 2020-02-19 22:48:29
@YRZ001030 用洛谷 IDE 跑跑看
by YRZ001030 @ 2020-02-19 22:50:27
@syksykCCC 也可以过样例。我寻思第一组数据应该就是样例吧/55
by YRZ001030 @ 2020-02-19 23:31:23
我顶 在顶
by YRZ001030 @ 2020-02-19 23:42:07
菜菜来结贴了 Q.size()为减1,就做下标使用了 然后合并函数的两个循环下标没有自增了。