Pagini recente » Cod sursa (job #2361360) | Cod sursa (job #1733739) | Cod sursa (job #1281535) | Cod sursa (job #1281533) | Cod sursa (job #2333475)
#include <bits/stdc++.h>
#define DIM 120001
using namespace std;
int st1[DIM],st2[DIM];
struct punct{
double x,y;
};
punct v[DIM];
bool cmp(punct a,punct b) {
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
double cross(int p0,int p1,int p2) {
return (v[p1].x-v[p0].x)*(v[p2].y-v[p0].y)-(v[p2].x-v[p0].x)*(v[p1].y-v[p0].y);
}
int main()
{ int nr1,nr2,i,n;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for (i=1;i<=n;++i)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
st1[1]=1,st1[2]=2;
nr1=2;
for (i=3;i<=n;++i) {
while (nr1>=2 && cross(st1[nr1-1],st1[nr1],i)<0)
--nr1;
st1[++nr1]=i;
}
st2[1]=n,st2[2]=n-1;
nr2=2;
for (i=n-2;i>=1;--i) {
while (nr2>=2 && cross(st2[nr2-1],st2[nr2],i)<0)
--nr2;
st2[++nr2]=i;
}
g<<nr1+nr2-2<<'\n';
for (i=1;i<=nr1;++i)
g<<setprecision(12)<<fixed<<v[st1[i]].x<<" "<<v[st1[i]].y<<'\n';
for (i=2;i<nr2;++i)
g<<setprecision(12)<<fixed<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';
return 0;
}