Pagini recente » Cod sursa (job #1440661) | Cod sursa (job #3288525) | Cod sursa (job #2938986) | Cod sursa (job #119721) | Cod sursa (job #1409688)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define N 120100
#define eps 1e-12
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int vf,i,n,p,st[N],viz[N];
struct punct{double x,y;}v[N];
inline double sarrus(punct a, punct b, punct c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline bool cmp(punct a, punct b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
f >> n;
for(i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
st[1] = 1;
st[2] = 2;
viz[2] = 1;
vf = 2;
for(i = 3, p = 1; i; i += p)
if(!viz[i])
{
if(i == n)
p = -1;
while(vf >= 2 && sarrus(v[st[vf - 1]], v[st[vf]], v[i]) < eps)
viz[st[vf--]] = 0;
st[++vf] = i;
viz[i] = 1;
}
g << vf - 1 << '\n';
for(i = 1; i < vf; ++i)
g << fixed << setprecision(9) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
return 0;
}