Pagini recente » Cod sursa (job #1036311) | Cod sursa (job #2545036) | Cod sursa (job #1787358) | Cod sursa (job #2645677) | Cod sursa (job #296559)
Cod sursa(job #296559)
#include<stdio.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define pdd pair<double,double>
#define mp make_pair
#define x first
#define y second
#define N 120010
const double eps=1e-12;
int n,k;
pdd v[N];
int st[N];
bitset<N> uz;
inline char cmp(double a,double b)
{
if(a+eps<b)
return -1;
if(b+eps<a)
return 1;
return 0;
}
inline char semn(pdd a,pdd b,pdd c)
{
double A=a.y-b.y,B=b.x-a.x,C=a.x*b.y-b.x*a.y;
return cmp(A*c.x+B*c.y+C,0);
}
bool compar(const pdd &a,const pdd &b)
{
char aux=cmp(a.x,b.x);
if(aux)
return (aux==-1);
return (cmp(a.y,b.y)==-1);
}
inline void citire()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,compar);
}
inline void rezolva()
{
k=2;
uz[2]=true;
st[1]=1;
st[2]=2;
int i=3,pas=1;
while(!uz[1])
{
while(uz[i])
{
if(i==n)
pas=-1;
i+=pas;
}
while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
uz[st[k--]]=false;
st[++k]=i;
uz[i]=true;
}
}
inline void scrie()
{
printf("%d\n",k-1);
for(int i=1; i<k; ++i)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
rezolva();
scrie();
return 0;
}