글 읽기 - 두코드의 차이점을 모르겠습니다

kyb1208tg 1년 전 0

윗코드는 정상적으로 통과가 되지만 아래코드는 시간초과로 계속 실패합니다.

어느 부분이 다른건지 알수있을까요?

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct Point {
    int x, y;
};
bool cmp_x(const Point &u, const Point &v) {
    return make_pair(u.x, u.y) < make_pair(v.x, v.y);
}
bool cmp_y(const Point &u, const Point &v) {
    return make_pair(u.y, u.x) < make_pair(v.y, v.x);
}
int dist(Point p1, Point p2) {
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
int brute_force(vector<Point> &a, int start, int end) {
    int ans = -1;
    for (int i=start; i<=end-1; i++) {
        for (int j=i+1; j<=end; j++) {
            int d = dist(a[i], a[j]);
            if (ans == -1 || ans > d) {
                ans = d;
            }
        }
    }
    return ans;
}
int closest(vector<Point> &a, int start, int end) {
    int n = end-start+1;
    if (n <= 3) {
        return brute_force(a, start, end);
    }
    int mid = (start + end) / 2;
    int left = closest(a, start, mid);
    int right = closest(a, mid+1, end);
    int ans = min(left, right);
    vector<Point> b;
    for (int i=start; i<=end; i++) {
        int d = a[i].x - a[mid].x;
        if (d*d < ans) {
            b.push_back(a[i]);
        }
    }
    sort(b.begin(), b.end(), cmp_y);
    int m = b.size();
    for (int i=0; i<m-1; i++) {
        for (int j=i+1; j<m; j++) {
            int y = b[j].y - b[i].y;
            if (y*y < ans) { 
                int d = dist(b[i], b[j]);
                if (d < ans) {
                    ans = d;
                }
            } else {
                break;
            }
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    sort(a.begin(), a.end(), cmp_x);
    cout << closest(a, 0, n-1) << '\n';
    return 0;
}
/****************************************/
#include <iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
struct Point{
    int x,y;
};
bool cmp_x(const Point &a, const Point &b){
    return make_pair(a.x,a.y)<make_pair(b.x,b.y);
}
bool cmp_y(const Point &a, const Point &b){
    return make_pair(a.y,a.x)<make_pair(b.y,b.x);
}
int len(Point a, Point b){
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
int brute(vector<Point> &v, int s, int e){
    int ans=-1;
    for(int i=s;i<e;i++){
        for(int j=i+1;j<=e;j++){
            int ret=len(v[i],v[j]);
            if(ans==-1||ret<ans){
                ans=ret;
            }
        }
    }
    //cout<<s<<" "<<e<<" "<<ans<<"\n";
    return ans;
}
int go(vector<Point> &v, int s, int e){
    int n=e-s+1;
    if(n<=3){
        return brute(v,s,e);
    }
    int m=(s+e)/2;
    int min1=go(v, s, m);
    int min2=go(v, m+1, e);
    int ans=min(min1, min2);
    vector<Point> b;
    for(int i=s;i<=e;i++){
        int d=v[i].x-v[m].x;
        if(d*d<ans){
            b.push_back(v[i]);
        }
    }
    sort(b.begin(),b.end(),cmp_y);
    for(int i=0;i<b.size()-1;i++){
        for(int j=i+1;j<b.size();j++){
            int d=b[i].y-b[j].y;
            if(d*d<ans){
                int l=len(b[i],b[j]);
                if(l<ans){
                    ans=l;
                }
            } else{
                break;
            }
        }
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Point> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].x>>v[i].y;
    }
    sort(v.begin(),v.end(),cmp_x);
    cout<<go(v,0,n-1)<<"\n";
    return 0;
}

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

문제

문제

출처

ICPC

두코드의 차이점을 모르겠습니다

kyb1208tg 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말