Pagini recente » Cod sursa (job #3270544) | Cod sursa (job #1025595) | Cod sursa (job #1350391) | Cod sursa (job #2783480) | Cod sursa (job #1366772)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int maxn = 120005;
int n, minpos, st[maxn], top;
pair<double, double> p[maxn];
inline long double crossproduct(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
return 1LL * (b.first - a.first) * (c.second - a.second) - 1LL * (c.first - a.first) * (b.second - a.second);
}
struct classcomp {
inline bool operator () (const pair<int, int> &a, const pair<int, int> &b) const {
return crossproduct(p[1], a, b) < 0;
}
};
int main() {
fin >> n;
minpos = 1;
for(int i = 1 ; i <= n ; ++ i) {
fin >> p[i].first >> p[i].second;
if(p[i] < p[minpos])
minpos = i;
}
swap(p[minpos], p[1]);
minpos = 1;
sort(p + 2, p + n + 1, classcomp());
st[++ top] = 1;
for(int i = 2 ; i <= n ; ++ i) {
while(top >= 2 && crossproduct(p[i], p[st[top]], p[st[top - 1]]) < 0)
-- top;
st[++ top] = i;
}
fout << top << '\n';
fout << fixed << setprecision(6);
for(int i = top ; i >= 1 ; -- i)
fout << p[st[i]].first << ' ' << p[st[i]].second << '\n';
}