글 읽기 - 2261번 왜 틀린지 모르겠습니다.

jis3613 6년 전 0

제 생각엔 맞는것 같은데

자꾸만 틀렸다고 뜨네요.......

왜 그럴까요?

38~47번 줄을

copy(Lx, Lx + mid, Ly);

copy(Rx, Rx + (n-mid), Ry);

sort(Ly, Ly + mid, cmpY);

sort(Ry, Ry + (n-mid), cmpY);

로 바꾸면 맞았다고 뜨거든요, 왜 그런지 잘 모르겠습니다.

도와주세요~ㅠㅠ

#include <iostream>
#include <algorithm>


using namespace std;

struct point{
    int x=0;
    int y=0;
};

int dist(point &p, point &q) {return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);}
bool cmpX(point &p, point &q) {return p.x < q.x;}
bool cmpY(point &p, point &q) {return p.y < q.y;}

int closestPair(point *Px, point *Py, int n) {
    if(n==2) return dist(Px[0],Px[1]);
    if(n==3) return min({dist(Px[0],Px[1]),dist(Px[1],Px[2]),dist(Px[2],Px[0])});
    
    int mid = n/2;
    int l= (Px[mid-1].x+Px[mid].x)/2;
    
    point Lx[mid];
    point Rx[n-mid];

    point Ly[mid];
    point Ry[n-mid];
    
    //dividing Px into Lx and Rx
    for(int i=0;i<n;i++){
        if(i<mid){
            Lx[i]=Px[i];
        }else{
            Rx[i-mid]=Px[i];
        }
    }
    
    //Ly and Ry are the lists of the points in Lx and Rx, sorted by the y-coords
    int j=0;
    int k=0;
    for(int i=0;i<n;i++){
        if (Py[i].x<=Lx[mid-1].x){
            Ly[j++]=Py[i];
        }else{
            Ry[k++]=Py[i];
        }
    }
    
    //find the distance of closest pair from each sides
    int d = min(closestPair(Lx,Ly,mid), closestPair(Rx,Ry,n-mid));

    point S[n];
    int Sn = 0;
    
    //storing only points that has the distance less than d from the boundary l.
    for (int i=0; i<n; i++) {
        int xdis = l-Py[i].x;
        if (xdis*xdis <= d) S[Sn++] = Py[i];
    }
    
    //out of those points we look for 11 positions of points in the list that is sorted by y-coordinates.
    for(int i=0; i<Sn; i++){
        for(int j=i+1; j<Sn && j<=i+7;j++){
            d = min(d, dist(S[i], S[j]));
        }
    }
    
    return d;
}


int main(void) {

    int n;
    cin >> n;
    
    point P[n];
    for (int i=0; i<n; i++) scanf("%d %d", &P[i].x, &P[i].y);
    
    point Px[n];
    point Py[n];
    
    copy(P, P + n, Px);
    copy(P, P + n, Py);
    
    sort(Px, Px + n, cmpX);
    sort(Py, Py + n, cmpY);
    
    int ans = closestPair(Px, Py, n);
    
    cout << ans;
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2261번 왜 틀린지 모르겠습니다.

jis3613 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말