글 읽기 - 2261번 문제 의도

Diuven 5년 전 3

2261번 가장 가까운 점 찾기 문제에서, 지금 숏코딩 상위권들의 코드를 보면 x축으로 정렬 후 뒤의 점을 x값으로만 커팅하면서 보는데, 이러면 O(n^2)인 것으로 알고 있습니다.

근데 사실 이 문제에서는 이렇게 봐도 좌표제한이 걸려 있어서 최악의 경우에도 10000*10000*10~=10^9 정도 계산량으로 통과가 되는데, 원래 문제 의도가 이런건가요?

알고리즘 분류에는 라인 스위핑하고 분할정복이 있길래, 뭔가 이상해서 질문드립니다.

// 그 코드

for(int i=1; i<=n; i++){
    for(int j=i+1; j<=n; j++){
        int x=P[j].x-P[i].x, y=P[j].y-P[i].y, d=x*x+y*y;
        if(x*x>=ans) break;
        ans=min(ans, d);
    }
}

chogahui05 5년 전 0

저게 어떻게 통과하는지 의문이네요..

x축이 같고 y축이 전부 다른 데이터를 넣기만 해도 시간초과가 날 거 같네요.

Diuven 5년 전 0

사실 저도 그렇게 클레임을 넣으려고 했었는데, 좌표 절대값이 전부 10000이하라서, 10^5개 데이터를 어떻게 할 수가 없어요... 제가 생각했던 데이터는 x값 1차이나고 y값은 2차이나는, 지그재그로 점이 있는, 그런 데이터였는데 할려고보니 좌표 제한이 있더군요.

그래서 데이터를 최대한 집약시켜놔도 한 x값에 최대 10^4개정도, 그래서 적어도 10개 x값은 있어야되고, 인접한 x값끼리 전부 본다고 해도 10^9정도밖에 되질 않아요.

근데 방금 이런 데이터로 해보니 1.970 초가 나오네요. 이걸로도 충분하겠습니다.

데이터 추가 부탁드립니다!

#include <bits/stdc++.h>
int main(){
    puts("100000");
    for(int i=0; i<10; i++)
    	for(int j=-10000; j<10000; j+=2)
    		printf("%d %d\n", i, j+i%2);
    return 0;
}

startlink 5년 전 1

데이터를 추가했습니다.

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

문제

문제

출처

ICPC

2261번 문제 의도

Diuven 5년 전 3

chogahui05 5년 전 0

Diuven 5년 전 0

startlink 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말