Pagini recente » Cod sursa (job #1614669) | Cod sursa (job #3243047) | Cod sursa (job #2425221) | Cod sursa (job #2961197) | Cod sursa (job #927345)
Cod sursa(job #927345)
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define max 120005
typedef pair<double,double> point;
int n,head;
point v[max],stack[max];
double cross_product(const point &a,const point &b,const point &c)
{
return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}
int comp(const point &a,const point &b)
{
return cross_product(v[1],a,b)<0;
}
void Read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&v[i].first,&v[i].second);
}
void Sort_Points()
{
int pos=1;
for(int i=2;i<=n;i++) if(v[i]<v[pos]) pos=i;
swap(v[1],v[pos]);
sort(v+2,v+n+1,comp);
}
void Solve()
{
Sort_Points();
stack[1]=v[1];
stack[2]=v[2];
head=2;
for(int i=3;i<=n;++i)
{
while( head>=2 && ( cross_product(stack[head-1],stack[head],v[i]) > 0 ) )
--head;
stack[++head]=v[i];
}
}
void Print()
{
printf("%d\n",head);
for(int i=head;i>=1;i--)
printf("%.9lf %.9lf\n",stack[i].first,stack[i].second);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Read();
Solve();
Print();
return 0;
}