글 읽기 - CPP 라인스위핑으로 구현했지만 시간 초과가 나옵니다.

radh1021 3년 전 0

다른 질문들을 찾아보면서 정렬 순서등을 확인해봤지만, 무엇이 문제인지 모르겠습니다.

도와주시면 감사하겠습니다.

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>

using namespace std;

int n;
vector<pair<int,int>> ipn; // pair(y좌표, x좌표)
int min_dist = INT_MAX;
bool cmp1(pair<int,int> a, pair<int,int> b){
    if(a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}
int dist(pair<int,int> a, pair<int,int> b){
    return (a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second);
}
int main(){
    cin >> n;
    ipn.resize(n);
    for(auto& it : ipn) cin >> it.second >> it.first;
    sort(ipn.begin(),ipn.end(),cmp1);
    ///*DEBUG*/for(auto it : ipn) cout << it.second <<","<< it.first << " ";
    
    set<pair<int,int>> val = {ipn[0], ipn[1]};
    
    min_dist = dist(ipn[0],ipn[1]);
    
    for(int i = 2; i < n ; i++){
        for( auto it = val.begin(); it != val.end();){ // x좌표 먼 것들 없애줌
            int x_dist = ipn[i].second - it->second;
            if(x_dist*x_dist > min_dist) it = val.erase(it);
            else{
                it++;
            }
        }
        int y_dist = (int)sqrt(min_dist)+1;
        auto valbg = val.lower_bound(pair<int,int>(ipn[i].first-y_dist,INT_MIN));
        auto valed = val.upper_bound(pair<int,int>(ipn[i].first+y_dist,INT_MAX));
        
        for(;valbg != valed; valbg++){ 
            int tmp_dist = dist(ipn[i],*valbg);
            if(tmp_dist < min_dist) min_dist=tmp_dist;
        }
        // y 좌표 먼 것들 제외함

        val.insert(ipn[i]);
        ///*DEBUG*/for(auto it : val) cout << it.second <<","<< it.first << " "; cout<<"\n";
    
    }
    cout << min_dist << "\n";
}

herdson 3년 전 0

x좌표에서 먼 점을 없애주는 방식이 잘못되었습니다.

y기준 정렬로 된 셋을 순회하면 후보가 될 수 없는 점을 빠르게 골라낼 수 없습니다.

그 부분을 고치니까 정답이 뜨네요.

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

문제

문제

출처

ICPC

CPP 라인스위핑으로 구현했지만 시간 초과가 나옵니다.

radh1021 3년 전 0

herdson 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말