Pagini recente » Cod sursa (job #2633754) | Cod sursa (job #702721) | Cod sursa (job #10431) | Cod sursa (job #227376) | Cod sursa (job #2883402)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
using ld = long double;
using PII = pair < ld, ld >;
const int NMAX = 12e4 + 3;
int N;
PII v[NMAX];
int st[NMAX];
bool sel[NMAX];
static inline void Read()
{
fin >> N;
for(int i = 1; i <= N; ++i)
fin >> v[i].first >> v[i].second;
return;
}
static inline ld Det(PII a, PII b, PII c)
{
return (a.first * b.second + b.first * c.second + a.second * c.first
- c.first * b.second - b.first * a.second - c.second * a.first);
}
static inline void Solve()
{
sort(v + 1, v + N + 1);
st[0] = 2;
st[1] = 1;
st[2] = 2;
sel[1] = true;
sel[2] = true;
for(int i = 3; i <= N; ++i) {
while(st[0] >= 2 && Det(v[i], v[st[st[0]]], v[st[st[0] - 1]]) <= 0)
sel[st[st[0]--]] = false;
st[++st[0]] = i;
sel[i] = true;
}
for(int i = N; i > 0; --i) {
if(sel[i] == true)
continue;
while(st[0] >= 2 && Det(v[i], v[st[st[0]]], v[st[st[0] - 1]]) <= 0)
sel[st[st[0]--]] = false;
st[++st[0]] = i;
sel[i] = true;
}
fout << st[0] - 1 << '\n';
fout << setprecision(12) << fixed;
for(int i = st[0] - 1; i >= 1; --i) {
fout << v[st[i]].first << " " << v[st[i]].second << '\n';
}
return;
}
int main()
{
Read();
Solve();
return 0;
}