Pagini recente » Cod sursa (job #3297820) | Cod sursa (job #2717216) | Cod sursa (job #3001417) | Cod sursa (job #2692319) | Cod sursa (job #2084283)
#include <bits/stdc++.h>
#define x first
#define y second
#define Nmax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int sol[Nmax], n, k;
pair<double, double>p[Nmax];
bool cmp(pair<double, double>a, pair<double, double>b)
{
if(a.x == b.x)return a.y < b.y;
return a.x < b.x;
}
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);
//return (p[a].x * (p[b].y - p[c].y) - p[a].y * (p[b].x - p[c].x) + p[b].x * p[c].y - p[b].y * p[c].x);
}
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);
// for(int i = 1; i <= n ; i++)fout << p[i].x << " "<< p[i].y << '\n';
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';
return 0;
}