Pagini recente » Cod sursa (job #2793966) | Cod sursa (job #2318008) | Cod sursa (job #1984082) | Cod sursa (job #1341164) | Cod sursa (job #2276154)
#include <bits/stdc++.h>
#define NM 120002
#define x first
#define y second
using namespace std;
int n;
pair <double, double> v[NM];
vector <pair <double, double> > infs;
double det(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main()
{
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
fin >> n;
for(int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
infs.push_back(v[1]);
infs.push_back(v[2]);
for(int i = 3; i <= n; i++)
{
int l = infs.size();
while(l > 1 && det(infs[l - 2], infs[l - 1], v[i]) < 0)
{
l--;
infs.pop_back();
}
infs.push_back(v[i]);
}
for(int i = n - 1; i >= 2; i--)
{
int l = infs.size();
while(l > 1 && det(infs[l - 2], infs[l - 1], v[i]) < 0)
{
l--;
infs.pop_back();
}
infs.push_back(v[i]);
}
fout << infs.size() << "\n";
for(auto j : infs)
fout << fixed << setprecision(12) << j.x << " " << j.y << "\n";
fout << "\n";
return 0;
}