Pagini recente » Cod sursa (job #2246966) | Cod sursa (job #1279663) | Cod sursa (job #2747076) | Cod sursa (job #1719876) | Cod sursa (job #1182053)
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <list>
#include <bitset>
#include <ctime>
#include <climits>
#include <cassert>
#include <iomanip>
using namespace std;
const string file = "algsort";
const string inputF = file + ".in";
const string outputF = file + ".out";
const double epsilon = 1e-7;
#define LL long long
#define ULL unsigned long long
#define MOD1 666013
#define MOD2 666019
#define MOD3 1999999973
#define base 73
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef pair<long long, long long> ll;
typedef pair<double, double> dd;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<dd> vdd;
#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define for_c_it(container, it) for (auto it : container)
#define present(container, element) (container.find(element) != container.end())
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define zeroes(x) ((x ^ (x - 1)) & x)
#define maxn 200001
vdd V, st;
int N;
double crossProduct(const dd &A, const dd &B, const dd &C) {
return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}
bool cmp(const dd &p1,const dd &p2) {
return crossProduct(V[0], p1, p2) < 0;
}
int convexHull() {
int top, i;
st[0] = V[0];
st[1] = V[1];
top = 1;
for (i = 2; i < N; ++i) {
while (top >= 1 && crossProduct(st[top - 1], st[top], V[i]) > 0) {
--top;
}
++top;
st[top] = V[i];
}
return top;
}
int main() {
#ifndef INFOARENA
freopen("input.txt", "r", stdin);
#else
freopen(inputF.c_str(), "r", stdin);
freopen(outputF.c_str(), "w", stdout);
#endif
int i, top;
scanf("%d", &N);
V.resize(N);
st.resize(N);
for (auto &x: V) {
scanf("%lf %lf", &x.first, &x.second);
}
int pos = 0;
for (i = 1; i < N; ++i) {
if (V[i] < V[pos]) {
pos = i;
}
}
swap(V[0], V[pos]);
sort(V.begin() + 1, V.end(), cmp);
top = convexHull();
printf("%d\n", top + 1);
while(top >= 0) {
printf("%.9lf %.9lf\n", st[top].first, st[top].second);
--top;
}
return 0;
}