글 읽기 - 도저히 왜틀렸는지 모르겠습니다 .........

seonh4996 4년 전 0

예제를 돌려도 맞구 ㅜ 도저히 왜틀렸는지 모르겠습니다.

반례좀 알려주실수 있으실까요 ㅜㅜ

해결했습니다..

각도관련 함수들의 정확도를 높여줬더니 해결됬습니다.

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>


using namespace std;
using point = pair<int, int>;
vector<point> Points; 
point standard;

static void input(){
	int N;
	cin >> N; 
	
	for(int i = 0; i < N; i++){
		int a, b;
		cin >> a >> b;
		Points.push_back(make_pair(a,b));
	}
	
}

double findangle(point a){
	int ax = (a.first - standard.first);
	int ay = (a.second - standard.second);
	double a_angle = atan2(ay,ax);
    //기존 a_angle *=(double)180/3.14159;
	a_angle *=(double)180/3.141592;
	return a_angle;
}
bool cmpdot(point a, point b){
	if(a.second < b.second) return true;
	if(a.second == b.second) return a.first < b.first;
	return false;
}

bool cmp(point a, point b){
	double a_angle = findangle(a);
	double b_angle = findangle(b);
	
	if(a_angle < b_angle)return true;
    //기존 if(a_angle - b_angle < 0.00001)
	if(a_angle - b_angle < 0.0000001)return cmpdot(a,b);
	return false;
}


long long ccw(point a, point b, point c){
	
	long long t = 1LL*a.first * b.second + 1LL*b.first * c.second + 1LL*c.first * a.second;
	long long p = 1LL*b.first * a.second + 1LL*c.first * b.second + 1LL*a.first * c.second;
	return t-p;
}


static stack<point>& GrahamScan(vector<point>& Points){
	stack<point>* tconvexhullpoints = new stack<point>(); 
	
	sort(Points.begin(), Points.end(), cmpdot);
	standard = Points[0];
	sort(Points.begin()+1, Points.end(), cmp);
	
	tconvexhullpoints->push(Points[0]);
	tconvexhullpoints->push(Points[1]);
	
	for(int i = 2; i < Points.size(); i++){
		while(tconvexhullpoints->size() >= 2){
			
			point first,second,next;
			second = tconvexhullpoints->top();
			tconvexhullpoints->pop();
			first = tconvexhullpoints->top();
			next = Points[i];
			
			if(ccw(first,second,next) > 0){
				tconvexhullpoints->push(second);
				break;
			}
		}
			
		tconvexhullpoints->push(Points[i]);
		
	}
	
	
	return *tconvexhullpoints;
}




int main(){
	input();
	stack<point> t = GrahamScan(Points);
	cout << t.size();
	
}

eldpswp99 4년 전 0

정렬할때 외적이용해서 하시면 double안써도 long long으로 정렬 가능해요

seonh4996 4년 전 0

@eldpswp99

말씀하신게, 위의 코드처럼 각도를 구해서 정렬하는 게 아니라 외적을 이용해서 각도 정렬을 할수있다는 말씀인가요?

eldpswp99 4년 전 0

네 외적 이용하면 벡터 두개 있을때 반시계인지 시계인지 알 수 있는데,

그라함스캔 쓸 때 기준점으로 잡을 벡터 원점으로 설정하고 나머지 점들 다 기준점 원점으로 하는 위치벡터로 만든 다음에

위치벡터 p1 p2있다고 하면 p1 x p2 > 0이면 p1 반시계에 p2가 있다는 뜻이니까 이거 이용해서 정렬할 수 있어요

ll crossproduct(const Point& lhs,const Point& rhs)
{
	return 1LL * lhs.x * rhs.y - 1LL * lhs.y * rhs.x;
}

struct compbyangle{
	bool operator()(const Point& lhs,const Point& rhs)
	{
		ll crsproduct = crossproduct(lhs,rhs);
		if(crsproduct > 0) return true;
		if(crsproduct == 0) return lhs.dist() < rhs.dist();
		
		return false;
	}
};

sort(pt.begin(),pt.end(),compbyangle());

seonh4996 4년 전 0

@eldpswp99

오.. 한번 이용해봐야겠네요 .. 새로운 정보 알려주셔서 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

도저히 왜틀렸는지 모르겠습니다 .........

seonh4996 4년 전 0

eldpswp99 4년 전 0

seonh4996 4년 전 0

eldpswp99 4년 전 0

seonh4996 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말