Pagini recente » Cod sursa (job #2881930) | Cod sursa (job #1188230) | Cod sursa (job #441695) | Cod sursa (job #3281773) | Cod sursa (job #3133849)
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int n;
struct puncte
{
double x, y;
}v[120001];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double arie(puncte &a, puncte &b, puncte &c)
{
return a.x*b.y + b.x*c.y + c.x*a.y -a.y*b.x - b.y*c.x - c.y*a.x;
}
bool cmp(puncte &a, puncte &b)
{
return arie(v[1], a, b) > 0;
}
vector<puncte> hull;
int main()
{
fin >> n;
int ind = 0;
for(int i = 1; i <= n; ++ i)
{
fin >> v[i].x >> v[i].y;
if(i > 1)
if(v[i].x < v[1].x)
ind = i;
else if(v[i].x == v[1].x and v[i].y < v[1].y)
ind = i;
}
swap(v[ind], v[1]);
sort(v + 2, v + n + 1, cmp);
hull.push_back(v[1]);
hull.push_back(v[2]);
for(int i = 3; i <= n; ++ i)
{
while(hull.size() > 1 and arie(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) <= 0)
hull.pop_back();
hull.push_back(v[i]);
}
fout << hull.size() << '\n';
for(auto it : hull)
{
fout << fixed << setprecision(12) << it.x << ' ' << it.y << '\n';
}
return 0;
}