글 읽기 - 모르겠습니다.

gs25 2년 전 1

x값을 기준으로 정렬하고 가장 왼쪽 아래에 있는 점을 기준으로 반시계로 정렬했습니다. 거기에 가장 왼쪽에 일직선일 수 있는 점들은 다시 바꿔줬습니다. 디버깅을 해봐도 감이 잘 안잡힙니다. 도움 부탁드립니다 ㅠㅠ

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N, L;

struct Point {
	ll x, y;
	int i;
};
Point p[100001];

bool cmp1(const Point& a, const Point& b)
{
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}
ll ccw(const Point& a, const Point& b, const Point& c)
{
	return a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y;
}
bool cmp2(const Point& a, const Point& b)
{
	return ccw(p[0], a, b) > 0;
}

ll dist(Point a, Point b)
{
	return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

int st[100001], top;
void push(int n) { st[top++] = n; }

int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> p[i].x >> p[i].y;
			p[i].i = i;
		}
		//x좌표 기준으로 정렬
		sort(p, p + N, cmp1);
		//가장 왼쪽에 있는 점을 기준으로 반시계방향 정렬
		sort(p + 1, p + N, cmp2);

		int cnt = 0, i = N-1;
		while (ccw(p[0], p[N - 1], p[i]) == 0) {
			i--;
			cnt++;
		}
		reverse(p + N - cnt, p + N);
		for (int i = 0; i < N; i++) cout << p[i].i << " ";
		cout << "\n";
	}
}

gs25 2년 전 0

cmp2 가 0일때 예외처리해주면 됩니다.

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

문제

문제

출처

ICPC

모르겠습니다.

gs25 2년 전 1

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말