글 읽기 - 어떤 input에서 틀리게 나왔는지 알고 싶습니다.

ldg1291 7년 전 0

linesweeping을 이용한 코드인데...

어떤 input에서 틀렸는지 알고 싶습니다. 감사합니다

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>

using namespace std;

vector <pair<int, int> > arr;
set <pair<int, int> > candi;

bool sort_pred(const pair<int, int>& left, const pair<int, int>& right)
{
    return left.second < right.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(int argc, const char * argv[]) {
   
    int n;
    
    scanf("%d", &n);
    
    while (n--) {
        
        int a, b;
        
        scanf("%d %d", &a, &b);
        
        arr.push_back(make_pair(a, b));
    }
    
    sort(arr.begin(), arr.end());
    
    candi.insert(make_pair(arr[0].second, arr[0].first));
    candi.insert(make_pair(arr[1].second, arr[1].first));
    
    int d = dist(arr[0], arr[1]);

    int start = 0;
    
    for(int i=2; i<n; i++) {
        pair <int, int> now = arr[i];
        
        while(start < i) {
            pair<int, int> tmp = arr[start];
            int dx = now.first - tmp.first;
            if(dx*dx > d) {
                candi.erase(make_pair(arr[start].second, arr[start].first));
                start += 1;
            } else break;
        }
        
        pair<int, int> lower_point = make_pair(now.second - sqrt(d)-1, -1000000);
        pair<int, int> upper_point = make_pair(now.second + sqrt(d)+1, 1000000);
        auto lower = candi.lower_bound(lower_point);
        auto upper = candi.upper_bound(upper_point);
        for(auto i = lower ; i != upper ; i++) {
            int td = dist(now, *i);
            if(td < d) {
                d = td;
            }
        }
        candi.insert(make_pair(arr[i].second, arr[i].first));
    }
    
    printf("%d\n",d);
    
    return 0;
}

zlzmsrhak 7년 전 0

반례만 달라고 하셔서 반례만 드립니다. 틀린 이유까지 알고싶으시면 다시 댓글 달아주세요.

ldg1291 7년 전 0

감사합니다 혹시 틀린 이유를 알 수 있을까요??

zlzmsrhak 7년 전 0

candi라는 set이 y축 우선으로 정렬되어야 하는데, x축 우선으로 정렬이 되어있어서 lower_bound, upper_bound가 제대로 작동하지 않습니다.

reference를 보고 set에 compare 함수를 추가하거나, 정렬을 y축 우선으로 하고 set을 x축 우선으로 정하는 방법이 있습니다.

ldg1291 7년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

어떤 input에서 틀리게 나왔는지 알고 싶습니다.

ldg1291 7년 전 0

zlzmsrhak 7년 전 0

ldg1291 7년 전 0

zlzmsrhak 7년 전 0

ldg1291 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말