회원가입
로그인
Toggle navigation
문제
문제
전체 문제
문제 출처
단계별로 풀어보기
알고리즘 분류
새로 추가된 문제
새로 추가된 영어 문제
새로 추가된 문제 풀이
문제 순위
문제
푼 사람이 1명인 문제
아무도 못 푼 문제
최근 제출된 문제
최근 풀린 문제
랜덤
출처
ACM-ICPC
Olympiad
한국정보올림피아드
한국정보올림피아드시․도지역본선
전국 대학생 프로그래밍 대회 동아리 연합
대학교 대회
카카오 코드 페스티벌
Coder's High
ACM-ICPC
Regionals
World Finals
Korea Regional
Africa and the Middle East Regionals
Europe Regionals
Latin America Regionals
North America Regionals
South Pacific Regionals
문제집
대회
1
채점 현황
랭킹
게시판
그룹
블로그
강의
N
전체
공지
자유
질문
오타/오역/요청
게시판 공지
홍보
업데이트
글쓰기
두 소스가 어떻게 다른 답을 내는지 궁금하네요...
13310번 - 먼 별
khsoo01
2년 전
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); }
댓글을 작성하려면
로그인
해야 합니다.
khsoo01 2년 전
sort(a+2, a+1+n, comp);
sort(a+1, a+1+n, comp);