Pagini recente » Cod sursa (job #59824) | Cod sursa (job #60032) | Cod sursa (job #2890854) | Cod sursa (job #1048280) | Cod sursa (job #1968465)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax = 12e4 + 10;
int n;
pair < double, double > p[nmax];
vector < int > st;
void input() {
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> p[i].x >> p[i].y;
}
double det(int a, int b, int c) {
return p[a].x * (p[b].y - p[c].y) + p[b].x * (p[c].y - p[a].y) + p[c].x * (p[a].y - p[b].y);
}
bool out(int a, int b, int c) {
return (det(a, b, c) > 0);
}
void run_convexhull() {
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; ++i) {
while (st.size() > 1 && out(st[st.size()-2], st[st.size()-1], i))
st.pop_back();
st.push_back(i);
}
for (int i = n - 1; i; --i) {
while (st.size() > 1 && out(st[st.size()-2], st[st.size()-1], i))
st.pop_back();
st.push_back(i);
}
st.pop_back();
}
void output() {
fout << st.size() << '\n';
fout << fixed << setprecision(10);
for (auto &it: st)
fout << p[it].x << ' ' << p[it].y << '\n';
}
int main() {
input();
run_convexhull();
output();
return 0;
}