글 읽기 - 단순 다각형 - Convex hull 문제입니다

alohajihwan 7년 전 0

안녕하세요.. 단순 다각형 문제가 안풀려 질문 드립니다.

Convex hull의 일부분을 이용해서 문제를 풀었습니다.

다각형이 되기위해 기준점(y 좌표 제일 작은 점) 과 각 점간의 각도가 큰것 순으로 정렬하여 출력하였습니다.

제가 예상 하기론 double 의 오차에서 틀렸습니다가 뜨는 거 같은데 답변 부탁드립니다.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<string>
#include<map>
#include<string.h>
#include<stack>
#include<fstream>
#include<set>
using namespace std;
#define ll long long
#define INF 987654321

struct node {
	double r;
	double x, y;
	int i;
	
	bool operator <(const node & other)const {
		if (r != other.r) {
			return r > other.r;
		}
		else {
			if (y != other.y) return y < other.y;
			else return x < other.x;
		}
	}
}arr[2222];

double dist(node A, node B)
{
	return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
// 기준점 A 와 다른 점 B의 각도 구하기
double angle(node A, node B)
{
	return (B.x - A.x) / dist(A, B);
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			scanf("%lf%lf", &arr[i].x, &arr[i].y);
			arr[i].i = i;
			arr[i].r = 0;
		}
        //기준점 찾기
		sort(arr, arr + n);
		for (int i = 1; i < n; i++) {
			arr[i].r = angle(arr[0], arr[i]);
		}	
        //기준점 제외 기준점 과의 각도 정렬
		sort(arr + 1, arr + n);
		for (int i = 0; i < n; i++) {
			cout << arr[i].i << " ";
		}
		cout << endl;
	}
}

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

문제

문제

출처

ICPC

단순 다각형 - Convex hull 문제입니다

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말