Pagini recente » Cod sursa (job #2927882) | Cod sursa (job #427632) | Cod sursa (job #548529) | Cod sursa (job #1699644) | Cod sursa (job #2175658)
#include <bits/stdc++.h>
#define Nmax 120002
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n;
struct puncte{
double x,y;
}v[Nmax];
int i,st[Nmax],vf,semn = 1;
bool seen[Nmax];
inline void read()
{
f >> n;
for(i = 1;i <= n;i++)
f >> v[i].x >> v[i].y;
}
bool cmp(puncte a,puncte b)
{
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double determinant(int a,int b,int c)
{
return v[a].x*v[b].y + v[b].x*v[c].y + v[c].x*v[a].y -
v[c].x*v[b].y - v[a].x*v[c].y - v[b].x*v[a].y;
}
int main()
{
read();
sort(v + 1,v + n + 1,cmp);
st[1] = 1;
st[2] = 2;
vf = 2;
for(i = 3;i >= 1;i += semn)
{
if(seen[i])
continue;
while(vf > 1 && determinant(st[vf - 1],st[vf],i) < 0)
seen[st[vf]] = 0 ,vf--;
st[++vf] = i; seen[i] = 1;
if(i == n)
semn = -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;
}