Pagini recente » Cod sursa (job #2066021) | Cod sursa (job #107895) | Cod sursa (job #353894) | Cod sursa (job #598487) | Cod sursa (job #2081575)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define pdd pair<double, double>
#define x first
#define y second
const int Nmax = 1200000 + 5;
pdd p[Nmax];
int n, sol[Nmax], k;
bool cmp(pdd a1, pdd a2)
{
if(a1.y == a2.y)return a1.x < a2.x;
return a1.y < a2.y;
}
double det(int a, int b, int c)
{
return (p[b].x - p[a].x) * (p[c].y - p[a].y) - (p[c].x - p[a].x) * (p[b].y - p[a].y);
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1, cmp);
sol[1] = 1; sol[2] = 2;
k = 2;
for(int i = 3; i <= n; ++i)
{
while(k > 1 && det(sol[k - 1], sol[k], i) < 0)
k --;
sol[++k] = i;
}
for(int i = n - 1; i >= 1; --i)
{
while(k > 1 && det(sol[k - 1], sol[k], i) < 0)
k --;
sol[++k] = i;
}
fout << k - 1 << '\n';
for(int i = 1; i < k; ++i)
fout << fixed << setprecision(12) << p[sol[i]].x << " " << p[sol[i]].y << '\n';
}