Pagini recente » Cod sursa (job #2206179) | Cod sursa (job #2925520) | Cod sursa (job #638770) | Cod sursa (job #1801727) | Cod sursa (job #2203576)
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100009
#define MMAX 200009
#define kInf (1 << 30)
#define kInfLL (1LL << 60)
#define kMod 666013
#define edge pair<int, int>
#define x first
#define y second
#define USE_FILES "MLC"
#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif
// number of tests from "in"
int test_cnt = 1;
void clean_test();
// your global variables are here
int N, posMin = 1, stackSz = 0;
pair <double, double> points[NMAX], st[NMAX];
double crossedProd(const pair <double, double> &a, const pair <double, double> &b, const pair <double, double> &c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(const pair <double, double> &p1, const pair <double, double> &p2) {
return crossedProd(points[1], p1, p2) < 0;
}
// your solution is here
void solve() {
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> points[i].first >> points[i].second;
if (points[i].first < points[posMin].first) {
posMin = i;
} else if (points[i].first == points[posMin].first && points[i].second < points[posMin].second) {
posMin = i;
}
}
swap(points[1], points[posMin]);
sort(points + 1, points + N + 1, cmp);
st[++stackSz] = points[1];
st[++stackSz] = points[2];
for (int i = 3; i <= N; ++i) {
while (stackSz > 1 && crossedProd(st[stackSz - 1], st[stackSz], points[i]) > 0) {
--stackSz;
}
st[++stackSz] = points[i];
}
cout << stackSz << '\n';
cout << fixed << setprecision(6);
for (int i = stackSz; i > 0; --i) {
cout << st[i].first << ' ' << st[i].second << '\n';
}
if (test_cnt > 0) {
clean_test();
}
}
void clean_test() {
// clean if needed
}
int main() {
// cin >> test_cnt;
while (test_cnt--) {
solve();
}
return 0;
}