Pagini recente » Cod sursa (job #4646) | Cod sursa (job #2262620) | Cod sursa (job #741952) | Cod sursa (job #2591921) | Cod sursa (job #1144657)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
typedef vector<int>::iterator iter;
#define MAXN 120005
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, pi = 1;
pair<double, double> pt[MAXN];
vector<int> ind, sol;
inline bool cmp(int a, int b) {
return (double)(pt[a].first - pt[pi].first) * (pt[b].second - pt[pi].second) < (double)(pt[b].first - pt[pi].first) * (pt[a].second - pt[pi].second);
}
bool sgn (int a, int b, int c) {
return ((long double)pt[a].first * pt[b].second + pt[b].first * pt[c].second + pt[c].first * pt[a].second - pt[a].second * pt[b].first - pt[b].second * pt[c].first - pt[c].second * pt[a].first) > 0;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> pt[i].first >> pt[i].second;
if (pt[pi].first > pt[i].first || (pt[pi].first == pt[i].first && pt[pi].second > pt[i].second)) {
pi = i;
}
}
for (int i = 1; i <= n; i++) {
if (i != pi) {
ind.push_back(i);
}
}
sort(ind.begin(), ind.end(), cmp);
for (iter it = ind.begin(); it != ind.end(); it++) {
while (sol.size() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), *it)) {
sol.pop_back();
}
sol.push_back(*it);
}
sol.push_back(pi);
reverse(sol.begin(), sol.end());
g << sol.size() << '\n';
for (iter it = sol.begin(); it != sol.end(); it++) {
g << pt[*it].first << ' ' << pt[*it].second << '\n';
}
f.close();
g.close();
return 0;
}