为何本地可以,提交一片re呀

P1429 平面最近点对(加强版)

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,就做下标使用了 然后合并函数的两个循环下标没有自增了。


|