Pagini recente » Cod sursa (job #1524160) | Cod sursa (job #396861) | Cod sursa (job #1092266) | Cod sursa (job #435075) | Cod sursa (job #1594907)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cstdio>
#include <iomanip>
using namespace std;
#define mp make_pair
#define x first
#define y second
#define eps 0.000001
#define inf 1 << 31
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i,j,n,m,k;
pair<double,double> v[120005],rasp[120005];
bool ok(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
return(a.x * b.y + b.x * c.y + c.x * a.y - ( b.y * c.x + c.y * a.x + a.y * b.x ) ) <= 0;
}
int main()
{
fin >> n;
for(i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v+1, v+1+n);
for(i = 1; i <= n; i++)
{
while(j > 1 && ok(rasp[j - 1], rasp[j], v[i]))
j--;
j++;
rasp[j] = v[i];
}
k = j;
for(i = n - 1; i > 0; i--)
{
while(j > k && ok(rasp[j - 1], rasp[j], v[i]))
j--;
j++;
rasp[j] = v[i];
}
j--;
fout << setprecision(6) << fixed;
fout << j << '\n';
for(i = 1; i <= j; i++)
fout << rasp[i].x<<" "<<rasp[i].y<<'\n';
return 0;
}