Pagini recente » Cod sursa (job #1857429) | Cod sursa (job #1878421) | Cod sursa (job #1431777) | Cod sursa (job #1816485) | Cod sursa (job #1918112)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
pair < double,double > v[120005];
bool ok;
int st[120005];
int x,n,i , poz,vf;
double unghi(const pair < int,int > &a,const pair < int,int > &b,pair < int,int > c)
{
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);;
}
bool cmp(const pair<int,int > &a,const pair < int,int > &b)
{
return (unghi(v[1],a,b) < 0);
}
int main()
{
f >> n;
poz = 1;
for(i = 1; i <= n; i++)
{
f >> v[i].first >> v[i].second;
if(v[poz] > v[i])
poz = i;
}
swap(v[1],v[poz]);
sort(v + 2,v + n + 1 ,cmp);
st[1] = 1;
st[2] = 2;
vf = 2;
i = 3;
while(i <= n)
{
while(vf > 2 && unghi(v[st[vf - 1]],v[st[vf]] , v[i]) > 0)
vf--;
st[++vf] = i;
i++;
}
g << vf << '\n';
g << fixed << setprecision(6) ;
while(vf)
g << v[st[vf]].first << " " << v[st[vf]].second << '\n' ,vf--;
return 0;
}