글 읽기 - 채점중 95%에서 시간초과가 납니다.

plzrun 8년 전 0

어디부분이 문제일까요?

아마 마지막 입력부분을 처리하지 못해서 시간초과가 나는것 같습니다.

문제를 푼 방법은, 둘로 쪼갠다음 중간부분만 처리했습니다.

먼저 두개를 쪼개서 얻은 (최소 거리)^2을 d라고 하면,

sqrt(d)+1을 sqrtd라고 하였습니다.

그리고 중간 좌표값 co[mid]로 부터 i를 하나씩 감소시키고, j는 하나씩 증가시키면서

이중 for문을 돌려서 x좌표의 차이가 d이하일때까지만 돌리도록 하였습니다.

그러면 이중 포문에서 거의 몇개 돌지도 않고 반복문을 빠져나올 것으로 예상이 되는데요.

아무튼 이렇게 해서 계속 거리를 구해서 d값을 업뎃합니다.

아마 같은 수 10만개가 들어왔을때 시간초과가 뜨는듯 한데, (이 이중포문을 다 도니까...? ㅠ)

어떻게 해결해야 할까요??

#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
struct Coord{
    int x, y;
    bool operator<(const Coord& rhs) const {
        if(x == rhs.x) {
            return y < rhs.y;
        } else return x < rhs.x;
    }
    bool operator==(const Coord& rhs) const {
        if(x==rhs.x && y==rhs.y) return true;
        else return false;
    }
}co[100001];

int spow(Coord& cos, Coord& coe) {
    if(cos == coe) return 0LL;
    return (coe.x-cos.x)*(coe.x-cos.x)+(coe.y-cos.y)*(coe.y-cos.y);
}
int solve(int s, int e) {
    if(s==e) return 0;
    if(s+1==e) {
        return spow(co[e], co[s]);
    }
    int mid = (s+e)/2;
    int t, d = spow(co[e], co[s]);
    if(s!=mid)
        if(d > (t=solve(s, mid))) d=t;

    if(e!=mid+1)
        if(d > (t=solve(mid+1, e))) d=t;

    int i, j;
    for(i=mid; i>=s; i--) {
        for(j=mid+1; j<=e; j++) {
            t = co[j].x-co[i].x;
            if(t*t > d) {
                break;
            } else {
                t = spow(co[j],co[i]);
                if(d > t) d=t;
            }
        }
        if(j == mid+1) break;
    }
    return d;
}
int main() {
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d %d", &co[i].x, &co[i].y);
    }
    sort(co, co+n);
    printf("%d", solve(0, n-1));
    return 0;
}

plzrun 8년 전 0

해결했어요... t*t==d일때에도 break를 넣어주었더니 시간안에 들어왔습니다 ㅠ

kimgs0725 8년 전 0

감사합니다. 문제 푸는데 도움이 되었습니다.

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

문제

문제

출처

ICPC

채점중 95%에서 시간초과가 납니다.

plzrun 8년 전 0

plzrun 8년 전 0

kimgs0725 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말