글 읽기 - 그라함 스캔 질문

sgc109 7년 전 0

y좌표로 정렬한뒤 가장아래있는 아무점을 잡고 각도로 정렬한뒤 반시계방향인것만 추가하는식으로했습니다.

처음에 y좌표로 정렬할때 y좌표가 같은경우 x좌표로도 정렬해야하지않아도 된다고생각했는데 혹시나해서 y좌표가 같은경우

x좌표로도 정렬하도록 고쳐봤는데도 WA가 났습니다.

어디가 잘못된걸까요? 절반이상 맞다가 중간에 틀리네요..

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(0.0)*2;
const int MOD = 1000000007;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

struct vector2{
	double x,y;
	vector2(double x, double y):x(x),y(y){}
	vector2(){}
	bool operator<(const vector2& rhs) const{return y<rhs.y;}
	vector2 operator-(const vector2& rhs) const {return vector2(x-rhs.x,y-rhs.y);}
	double dot(vector2& rhs){return x*rhs.x+y*rhs.y;}
	double cross(const vector2& rhs){return x*rhs.y-y*rhs.x;}
	double size(){return sqrt(x*x+y*y);}
};
vector2 base;
double ccw(vector2& a, vector2& b, vector2& c){
	return (b-a).cross(c-a);
}
bool cmpAngle(const vector2& lhs, const vector2& rhs){
	vector2 unit = vector2(1,0);
	vector2 a = lhs-base;
	vector2 b = rhs-base;
	return a.dot(unit)/(a.size()*unit.size())>b.dot(unit)/(b.size()*unit.size());
}
int N,a,b;
vector<vector2> points;
vector<vector2> poly;
int main() {
	inp1(N);
	FOR(i,N){
		inp2(a,b);
		points.pb(vector2{(double)a,(double)b});
	}
	sort(all(points));
	base=points[0];
	points.erase(points.begin());
	sort(all(points),cmpAngle);
	poly.pb(base);
	poly.pb(points[0]);
	for(int i=1;i<sz(points);i++){
		while(poly.size()>=2&&ccw(poly[poly.size()-2],poly.back(),points[i])<=0) poly.pop_back();
		poly.pb(points[i]);
	}
	printf("%d",sz(poly));

	return 0;
}

dlwodnsdl 7년 전 1

좌표를 double로 받으시면 맨 아래점을 기준으로 여러점이 한 직선위에 있는 경우에 부동 소수점 오차때문에 여러번 세어지는 경우가 있습니다. 각도 관련해서는 일직선 위에 없다는 조건이 없다면 정수형으로 데이터를 받아야 합니다.

sgc109 7년 전 0

@dlwodnsdl 잘 이해가 가지않습니다 ㅠ 어느부분을 어떻게 고쳐야하나요?

예를 들어 (0,0), (3,1), (6,2)와 같이 세 점 이상이 한 직선 위에 있는 경우에 ccw의 함수값이 0이 나와야 합니다.
하지만 실수형 자료를 사용하는 경우 부동 소수점 오차때문에 음수나 양수 값이 나와서 같은 직선 위에 있음에도 시계방향 혹은 반시계방향으로 판단하기 때문에 점을 더 세는 경우가 발생합니다.
그러기 때문에 정수형 자료를 사용하고, 분수 꼴은 통분을 통해서 분자를 비교하는 방식등으로 정수형으로만 처리해야 합니다.

sgc109 7년 전 0

@dlwodnsdl 그렇군요. 그런데 저는 각도정렬을 할때 atan2(y,x) 를 쓰지않고 (1,0) 과의 내적을 이용해서 x축과 이루는 각도의 코사인값으로 정렬을 했는데 그래도 실수 오차가 문제가 될까요???

여러 질문글에서 답변해주신분들이 제시하시는 입력들을 다 넣어봤는데 맞는 값이나왔고 지금 (0,0) (3,1) (6,2) 도 맞게 나오는것같아서요..

sgc109 7년 전 0

아.. 어쨋든 저같은경우에도 cos 값을 구할때 내적값/(a의크기*b의크기) 이런식으로 나눠주는 부분이있기때문에 생길수밖에없는건가요?

sgc109 7년 전 0

임시적으로 코드를 이렇게 수정해보았습니다.

일직선상에 있을경우 거리로 정렬해주고

double 을 쓰지않고 벡터의 크기를 구하는부분은 제곱을해서 정수로 하도록했고

정렬하는부분의 부등식의 양변을 제곱하고 양변의 분모를 곱하는식으로 바꿔보았습니다.(양변의 부호가 다를수도있으므로 그걸 4가지경우로 나눠서 처리했습니다)

그런데 틀렸습니다가 나오네요.. 어디가 잘못된걸까요?

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(0.0)*2;
const int MOD = 1000000007;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

ll sqr(ll x){return x*x;}
struct vector2{
	ll x,y;
	vector2(ll x, ll y):x(x),y(y){}
	vector2(){}
	bool operator<(const vector2& rhs) const{return y<rhs.y;}
	vector2 operator-(const vector2& rhs) const {return vector2(x-rhs.x,y-rhs.y);}
	ll dot(vector2& rhs){return x*rhs.x+y*rhs.y;}
	ll cross(const vector2& rhs){return x*rhs.y-y*rhs.x;}
	ll size(){return x*x+y*y;}
};
vector2 base;
double ccw(vector2& a, vector2& b, vector2& c){
	return (b-a).cross(c-a);
}
bool cmpAngle(const vector2& lhs, const vector2& rhs){
	vector2 unit = vector2(1,0);
	vector2 a = lhs-base;
	vector2 b = rhs-base;
	if(sqr(a.dot(unit))*(b.size()*unit.size())==sqr(b.dot(unit))*(a.size()*unit.size())) return a.size()<b.size();
	if(a.dot(unit)<0&&b.dot(unit)>0) return false;
	if(a.dot(unit)>0&&b.dot(unit)<0) return true;
	if(a.dot(unit)<0&&b.dot(unit)<0) return sqr(a.dot(unit))*(b.size()*unit.size())<sqr(b.dot(unit))*(a.size()*unit.size());
	return sqr(a.dot(unit))*(b.size()*unit.size())>sqr(b.dot(unit))*(a.size()*unit.size());
}
int N;
ll a,b;
vector<vector2> points;
vector<vector2> poly;
int main() {
	inp1(N);
	FOR(i,N){
		scanf("%lld%lld",&a,&b);
		points.pb(vector2{a,b});
	}
	sort(all(points));
	base=points[0];
	points.erase(points.begin());
	sort(all(points),cmpAngle);
	poly.pb(base);
	poly.pb(points[0]);
	for(int i=1;i<sz(points);i++){
		while(poly.size()>=2&&ccw(poly[poly.size()-2],poly.back(),points[i])<=0) poly.pop_back();
		poly.pb(points[i]);
	}
	printf("%d",sz(poly));

	return 0;
}

sgc109 7년 전 0

@dlwodnsdl 오버플로우는 안나지않나요?? 최악의경우 16억*32억 일것같은데 512*10^16 은 long long 으로 처리가 되더라구요

dlwodnsdl 7년 전 0

base 값이 기준이기 때문에 8만 까지 가능하고 64억*128억으로 오버플로우가 발생합니다. 저렇게 기준 벡터를 잡아서 비교하시기 보다는 두벡터의 CCW를 활용하셔서 각도정렬을 해주면 되고요.
ccw함수도 long long int형으로 수정하셔야 합니다.
그리고 처음에 y좌표도 같은 경우에 x좌표 값으로도 정렬을 해주어야 theta 값이 (0,pi/2]나 [0,pi/2)로 겹치지 않을 것 같습니다.

사실 제가 C++에 익숙하지 않아서 C++로 수정해보려다가 포기하고 java로 변환해서 AC를 받았는데 혹시 저 위에거 수정해도 안되시면 메일 주소 남겨주시면 java 코드라도 보내드릴게요.

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

문제

문제

출처

ICPC

그라함 스캔 질문

sgc109 7년 전 0

dlwodnsdl 7년 전 1

sgc109 7년 전 0

dlwodnsdl 7년 전 0

sgc109 7년 전 0

sgc109 7년 전 0

sgc109 7년 전 0

sgc109 7년 전 0

dlwodnsdl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말