Pagini recente » Cod sursa (job #2298700) | Cod sursa (job #940055) | Cod sursa (job #285832) | Cod sursa (job #2722359) | Cod sursa (job #2280434)
#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;
bool u[NM];
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; i >= 1; i--)
if(det(v[i], infs[0], infs[1]) >= 0)
{
int l = infs.size();
while(l > 1 && det(infs[l - 2], infs[l - 1], v[i]) < 0)
{
l--;
infs.pop_back();
}
if(det(infs[l - 1], v[i], infs[0]) > 0)
infs.push_back(v[i]);
}
fout << infs.size() << "\n";
for(auto j : infs)
fout << fixed << setprecision(12) << j.x << " " << j.y << "\n";
return 0;
}