글 읽기 - 어디서 시간초과가 나는지 잘 모르겠어요..

112224 5년 전 0

https://www.acmicpc.net/blog/view/25을 공부해서 푸는 중인데

구조체를 정의하기보다 stl 멤버인 pair 를 사용하면 더 편하겠다 싶어서

pair 를 이용해서 푼 것 말고는 큰 차이가 생기지 않은 것 같은데

제 코드는 TLE가 뜨네요..

lower_bound,upper_bound 쪽에 혹시 문제가 있나요??

#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
/////////////////////////using line sweep////
typedef pair<int,int> ii;
ii a[100001];

int dist(ii &u,ii &v)
{
    return (u.first-v.first)*(u.first-v.first)+(u.second-v.second)*(u.second-v.second);
}
bool operator <(ii& u,ii&v)
{
    if(u.second==v.second)
    return u.first<v.first;
    
    return u.second<v.second;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i].first>>a[i].second;
    sort(a,a+n);                    // sorted by x 
    int ans=dist(a[0],a[1]);
    set <ii> candi = {a[0],a[1]};
    int start=0;
    for(int i=2;i<n;i++)
    {
        ii now=a[i];
        while(start<i)        //기존에 거른 범위에 대해서는 x
        {
            auto p = a[start];
            int nd=now.first-p.first;
            if(nd*nd>ans)
            {
                candi.erase(p);     //set에서도 제거
                start++;
            }
            else
            {
                break;
            }
        }
        int d=(int)sqrt((double)ans)+1; 
        auto lower_p=make_pair(-10000,now.second-d);    // lower,upper를 위한 기준
        auto upper_p=make_pair(10000,now.second+d);
        auto lower=candi.lower_bound(lower_p);
        auto upper=candi.upper_bound(upper_p);
        for(auto it=lower;it!=upper;it++)           //후보자 그룹의 lower to upper 까지만
        {
            ii t=*it;
            int nd=dist(now,t);
            ans=min(ans,nd);                //거리 갱신
        }
        candi.insert(now);
    }
    cout<<ans<<'\n';
    
}

djm03178 5년 전 1

pair<int, int>에 대한 < 연산자는 이미 pair 내부적으로 정의되어있는데 14번째 줄 같은 재정의 시 어떻게 되는지 정확히는 모르겠지만, 기존의 정의가 더 우세한 것 같습니다. set에서도 first를 second보다 먼저 비교하는 쪽을 택하는 것 같네요.

112224 5년 전 0

오 감사합니다! ㅠㅠ 디버깅 보고 있었는데 평상시 정렬이랑 똑같이 되있어서
생각도 못하고 있었습니다ㅠ
first,second 입력 바꿔서 받는 걸로 해결하였습니다.
질문게시판 보면서 항상 도움많이 받았는데 또 한번 감사드립니다!!

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

문제

문제

출처

ICPC

어디서 시간초과가 나는지 잘 모르겠어요..

112224 5년 전 0

djm03178 5년 전 1

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말