Pagini recente » Borderou de evaluare (job #2195586) | Borderou de evaluare (job #591721) | Borderou de evaluare (job #3119012) | Cod sursa (job #3268687) | Cod sursa (job #1400750)
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<double,double>
#define fi first
#define se second
using namespace std;
const double eps=0.0000000000001;
const int NMAX=120005;
int n,st[NMAX];
PII a[NMAX];
bitset<NMAX>viz;
//reduc formula la o suma,sa fiu sigur ca nu gresesc
inline double Semn(int x,int y,int z)
{
return (a[z].se*(a[y].fi-a[x].fi)+a[z].fi*(a[x].se-a[y].se)+a[x].se*(a[x].fi-a[y].fi)+a[x].fi*(a[y].se-a[x].se));
}
int main()
{
int i,top=2,val=1;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin.sync_with_stdio(false);
cin>>n;
for (i=1;i<=n;i++) cin>>a[i].se>>a[i].fi;
sort(a+1,a+n+1);
st[1]=1;st[2]=2;
viz[2]=1;
for (i=3;i>0;i+=val)
{
if (viz[i]==1) continue;
while (top>=2 && Semn(st[top],st[top-1],i)<eps)
{
viz[st[top]]=0;
top--;
}
st[++top]=i;viz[i]=1;
if (i==n) val=-1;
}
cout<<(top-1)<<"\n";
cout<<setprecision(12)<<fixed;
for (i=1;i<top;i++) cout<<a[st[i]].se<<" "<<a[st[i]].fi<<"\n";
return 0;
}