Pagini recente » Cod sursa (job #37734) | Cod sursa (job #724021) | Cod sursa (job #1656889) | Cod sursa (job #2947104) | Cod sursa (job #2930185)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
pair<double, double> v[120001], p0;
vector<int> ans;
int dist(pair<double, double>& x, pair<double, double>& y)
{
return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
}
int orient(pair<double, double> &a, pair<double, double> &b, pair<double, double> &c)
{
int l = a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second);
if (l > 0)
return 1;
else if (l < 0)
return -1;
else
return 0;
}
bool csort(pair<double, double> a, pair<double, double> b)
{
int r = orient(p0, a, b);
if (r == 0)
return dist(p0, a) < dist(p0, b);
else return r < 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
if (n < 3)
{
cout << "0";
return 0;
}
for (int i = 1; i <= n; i++)
{
cin >> v[i].first >> v[i].second;
if (p0.second > v[i].second || (p0.second == v[i].second && p0.first > v[i].first))
p0 = v[i];
}
sort(v + 1, v + 1 + n,csort);
int i = n;
while (i >= 0 && orient(p0, v[i], v[n]) == 0) i--;
reverse(v + i + 1, v + 1 + n);
for (int i = 1; i <= n; i++)
{
while (ans.size() > 1 && orient(v[ans[ans.size() - 2]], v[ans.back()], v[i]) > 0)
ans.pop_back();
ans.push_back(i);
}
reverse(ans.begin(),ans.end());
cout << ans.size() << '\n';
int l = 0;
for (int i = 0; i < ans.size(); i++)
{
if (v[ans[i]] == p0)
{
l = i;
break;
}
}
for (int i = l; i < ans.size(); i++)
cout << v[ans[i]].first << ' ' << v[ans[i]].second << '\n';
for (int i = 0; i < l; i++)
cout << v[ans[i]].first << ' ' << v[ans[i]].second << '\n';
return 0;
}