Pagini recente » Cod sursa (job #578423) | Cod sursa (job #2689026) | Cod sursa (job #1931051) | Cod sursa (job #1540597) | Cod sursa (job #1379472)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define eps 1e-12
#define N 120100
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,vf,pas,st[N],viz[N];
pair<double,double>v[N];
inline double Sarrus(pair<int,int> a, pair<int,int> b,pair<int,int> c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main()
{
f >> n;
for(i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
st[1] = 1;
st[2] = 2;
vf = 2;
viz[2] = 1;
pas = 1;
for(i = 1; i; i += pas)
if(!viz[i])
{
while(vf >= 2 && Sarrus(v[st[vf - 1]], v[st[vf]], v[i]) < eps)
viz[st[vf]] = 0,
--vf;
st[++vf] = i;
viz[i] = 1;
if(i == n)
pas = -1;
}
g << vf - 1 << '\n';
for(i = 1; i < vf; ++i)
g << fixed << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
return 0;
}