# Cod sursa(job #889535)

Utilizator Data 24 februarie 2013 16:10:32 Infasuratoare convexa 100 cpp done Arhiva educationala 1.4 kb
``````#include<fstream>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<ctime>
using namespace std;

clock_t start=clock();

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N;
pair<double, double>points[120009];

int vf;
int stiva[120009];

double semn(pair<double, double>p1, pair<double, double>p2, pair<double, double>p3)
{
return (p2.first - p1.first) * (p3.second - p1.second) - (p2.second - p1.second) * (p3.first - p1.first);
}

bool cmp(pair<double, double>p1, pair<double, double>p2)
{
return semn(points[1], p1, p2) > 0;
}

int main()
{
int i, j;

f>>N;
for(i = 1, j = 1; i <= N; i++)
{
f>>points[i].first>>points[i].second;
if(points[i].second < points[j].second)
j = i;
else if(points[i].second == points[j].second && points[i].first < points[j].first)
j = i;

}

swap(points[1], points[j]);
sort(points + 2, points + N + 1, cmp);

stiva[1] = 1; stiva[2] = 2; vf = 2;
i = 3;

while(i <= N)
{
if(vf < 2)
{	stiva[++vf] = i++;
continue;
}
if(semn(points[stiva[vf - 1]], points[stiva[vf]], points[i]) > 0)
stiva[++vf] = i++;
else vf--;
}

g<<vf<<'\n';
for(i = 1; i <= vf; i++)
g<<fixed<<setprecision(6)<<points[stiva[i]].first<<" "<<points[stiva[i]].second<<'\n';

cout << 1.0*(clock()-start)/(1.0*CLOCKS_PER_SEC) << '\n';

f.close();
g.close();
return 0;
}
``````