Pagini recente » Profil Adia_Ioana | Cod sursa (job #2296317) | Cod sursa (job #1581330) | Monitorul de evaluare | Cod sursa (job #2270036)
#pragma GCC optimize("O3")
#include <iostream>
#include <bits/stdc++.h>
#define pdd pair <double, double>
#define Nmax 120010
#define mp make_pair
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pdd points[Nmax];
vector < pdd > L;
double orientation(pdd q,pdd p,pdd r)
{
return (r.second - q.second) * (p.first - q.first) - (r.first - q.first) * (p.second - q.second);
}
bool cmp(pdd a,pdd b)
{
return orientation(points[1],a,b) > 0;
}
void sortare()
{
int pr = 1;
for (int i = 2; i <= n; i++)
if (points[i] < points[pr])
pr = i;
swap(points[1],points[pr]);
sort(points + 2, points + n + 1, cmp);
}
int main()
{
ios_base::sync_with_stdio(0);
fin.tie(0); fout.tie(0);
fin >> n;
for (int i = 1; i <= n; i++)
fin >> points[i].first >> points[i].second;
sortare();
L.push_back(points[1]);
L.push_back(points[2]);
for (int i = 3; i <= n; i++)
{
while (L.size() > 2 && orientation(L[L.size()-2],L[L.size()-1],points[i]) <= 0)
L.pop_back();
L.push_back(points[i]);
}
fout << L.size() << "\n";
fout << setprecision(9) << fixed;
for(auto a:L)
fout << a.first << " " << a.second << "\n";
return 0;
}