백준 소스코드 [C++] 2699 격자점 컨벡스헐

www.acmicpc.net/problem/2699

2699번: 격자점 컨벡스헐

백준 소스코드 [C++] 2699 격자점 컨벡스헐

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;
struct dot {
	ll x, y;
};
vector<dot> dots;

int ccw(dot A, dot B, dot C) {
	ll rot = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
	if (rot > 0) return 1;
	else if (rot < 0) return -1;
	else return 0;
}

ll dist(dot a, dot b) {
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
bool cmp(const dot& a, const dot& b) {
	int val = ccw(dots[0], a, b);
	if (val < 0) return true;
	if (val > 0) return false;
	if (dist(dots[0], a) < dist(dots[0], b)) return true;
	return false;
}
vector<dot> graham() {
	vector<dot> s;
	for (int i = 0; i < dots.size(); i++) {
		while (2 <= s.size() && ccw(s[s.size() - 2], s[s.size() - 1], dots[i]) >= 0)
			s.pop_back();
		s.push_back(dots[i]);
	}
	return s;
}

void convexhull() {
	int temp = 0;
	for (int i = 1;i < dots.size();i++)
		if (dots[i].y > dots[temp].y || (dots[i].y == dots[temp].y && dots[i].x < dots[temp].x))
			temp = i;
	swap(dots[temp], dots[0]);
	sort(dots.begin() + 1, dots.end(), cmp);
	vector<dot> res = graham();
	cout << res.size()<<'\n';
	for (int i = 0;i < res.size();i++)
		cout << res[i].x << " " << res[i].y << '\n';
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int n,t;
	cin >> t;
	while (t--) {
		cin >> n;
		dots.clear();
		dots.resize(n);
		for (int i = 0; i < n; i++)
			cin >> dots[i].x >> dots[i].y;
		convexhull();
	}
	return 0;
}