Pagini recente » Cod sursa (job #85131) | Cod sursa (job #589709) | Cod sursa (job #994122) | Cod sursa (job #913756) | Cod sursa (job #1249236)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
const double EPS=1e-12;
typedef struct lol {
double x,y;
}troll;
int st[120005],n,i,p,nr;
bool viz[120005];
troll a[120005];
double area(troll a,troll b,troll c) {
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(const troll &a,const troll &b) {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
st[1]=1; st[2]=2; viz[2]=1; nr=2;
for(i=1,p=1;i>0;i+=p)
{
if(!viz[i]) {
while(nr>=2 && area(a[st[nr-1]],a[st[nr]],a[i])<EPS)
viz[st[nr--]]=0;
st[++nr]=i; viz[i]=1;
}
if(i==n) p*=-1;
}
cout<<nr-1<<'\n';
cout<<setprecision(7)<<fixed;
for(i=1;i<nr;++i) cout<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
return 0;
}