글 읽기 - 두 소스가 어떻게 다른 답을 내는지 궁금하네요...

khsoo01 7년 전 0

첨부한 소스 코드는 제가 문제를 풀 때 사용한 소스의 일부입니다. (맞은 코드)

그런데, 여기서 get_hull 함수의

sort(a+2, a+1+n, comp);

부분을

sort(a+1, a+1+n, comp);

로 바꾸면 틀리는데요,

제가 생각하기로는 비교 함수에 a[1]이 들어가게 되면 항상 tmp가 0이 되고, dist(a[1], a[1]) == 0이기 때문에 항상 a[1]이 더 작거나 같다고 판정하게 되어서 a[1]의 위치가 변할 일은 없기 때문에 a[1]부터 정렬하든 a[2]부터 정렬하든 크게 다를 것이 없을 것 같습니다.

a[1]부터 정렬할 때와 a[2]부터 정렬할 때 발생하는 차이의 이유가 궁금합니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;

struct coord {
    ll x, y;
    bool operator < (const coord &C) const {
        if(y == C.y) return x < C.x;
        return y < C.y;
    }
} a[30005];

ll ccw (coord &A, coord &B, coord &C) {
    return (A.x*B.y + B.x*C.y + C.x*A.y) - (A.y*B.x + B.y*C.x + C.y*A.x);
}

ll sq (ll X) {
    return X*X;
}

ll dist (coord &A, coord &B) {
    return sq(A.x - B.x) + sq(A.y - B.y);
}

bool comp (coord &A, coord &B) {
    ll tmp = ccw(a[1], A, B);
    if(tmp == 0) return (dist(a[1], A) < dist(a[1], B));
    return (tmp > 0);
}

void get_hull () {
    swap(*min_element(a+1, a+1+n), a[1]);
    sort(a+2, a+1+n, comp);
}

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

문제

문제

출처

ICPC

두 소스가 어떻게 다른 답을 내는지 궁금하네요...

khsoo01 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말