Pagini recente » Cod sursa (job #2235421) | Cod sursa (job #2920024) | Cod sursa (job #3286800) | Cod sursa (job #3173926) | Cod sursa (job #3200083)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
using ll = long long;
struct pll
{
double x, y;
};
const double eps = 1e-6;
ll det(pll a, pll b, pll c)
{
double d = (a.x*b.y + b.x*c.y + c.x*a.y) - (b.y*c.x + c.y*a.x + a.y*b.x);
if(d == 0)
return 0;
if(d > 0)
return 1;
return -1;
}
const int NMAX = 120005;
pll v[NMAX];
ll n;
vector<int> lower, upper, hull;
void compute()
{
ll i;
lower.pb(1);
for(i = 2; i <= n; i++)
{
while(lower.size() >= 2 && det(v[lower[lower.size()-2]], v[lower[lower.size()-1]], v[i]) == -1)
lower.pop_back();
lower.pb(i);
}
upper.pb(1);
for(i = 2; i <= n; i++)
{
while(upper.size() >= 2 && det(v[upper[upper.size()-2]], v[upper[upper.size()-1]], v[i]) == 1)
upper.pop_back();
upper.pb(i);
}
upper.pop_back();
reverse(upper.begin(), upper.end());
for(i = 0; i < lower.size(); i++)
hull.pb(lower[i]);
for(i = 0; i < upper.size(); i++)
hull.pb(upper[i]);
}
signed main()
{
in >> n;
for(int i = 1; i <= n; i++)
{
in >> v[i].x >> v[i].y;
}
compute();
out << hull.size() - 1 << '\n';
for(int i = 0; i < hull.size() - 1; i++)
{
out << fixed << setprecision(6) << v[hull[i]].x << ' ';
out << fixed << setprecision(6) << v[hull[i]].y;
out << '\n';
}
return 0;
}