Pagini recente » Cod sursa (job #2774250) | Cod sursa (job #1307126) | Cod sursa (job #2249360) | Cod sursa (job #44696) | Cod sursa (job #2305456)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005;
int n,top;
int st[Nmax];
bitset<Nmax>viz;
struct el
{
double x,y;
bool operator <(const el &e)const
{
if(y==e.y)return x<e.x;
return y<e.y;
}
}a[Nmax];
inline double Semn(int A,int B,int pct)
{
return a[pct].x*(a[A].y-a[B].y)+a[pct].y*(a[B].x-a[A].x)+a[A].x*a[B].y-a[A].y*a[B].x;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
st[1]=1;
st[2]=2;
viz[2]=1;
for(int i=3;i<=n;i++)
{
while(top>=2 && Semn(st[top],st[top-1],i)<0)
{
viz[st[top]]=0;
top--;
}
st[++top]=i;
viz[i]=1;
}
for(int i=n-1;i>=1;i--)
if(!viz[i])
{
while(top>=2 && Semn(st[top],st[top-1],i)<0)
{
viz[st[top]]=0;
top--;
}
st[++top]=i;
viz[i]=1;
}
fout<<top<<"\n";
fout<<fixed<<setprecision(12);
for(int i=1;i<=top;i++)
fout<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
fin.close();
fout.close();
return 0;
}