Pagini recente » Cod sursa (job #1834191) | Cod sursa (job #409515) | Cod sursa (job #761120) | Cod sursa (job #876027) | Cod sursa (job #1929218)
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int nmax=120023;
pair<double,double>v[nmax];
double coord1=1000000003,coord2=1000000003;
int ind;
int n;
int stck[nmax];
int comp(const pair<double,double> &a,const pair<double,double> &b)
{
return (a.second-coord2)*(b.first-coord1)<(b.second-coord2)*(a.first-coord1);
}
double arie(double x1,double y1,double x2,double y2,double x3,double y3)
{
return (double)(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
}
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].first,&v[i].second);
if(coord1>v[i].first)
{
coord1=v[i].first;
coord2=v[i].second;
ind=i;
}
else if(coord1==v[i].first&&coord2>v[i].second)
{
coord2=v[i].second;
ind=i;
}
}
swap(v[1],v[ind]);
sort(v+2,v+n+1,comp);
stck[1]=1,stck[2]=2;
int ps=2;
for(int i=3;i<=n;i++)
{
while(arie(v[stck[ps-1]].first,v[stck[ps-1]].second,v[stck[ps]].first,v[stck[ps]].second,v[i].first,v[i].second)<0&&ps>=2) --ps;
stck[++ps]=i;
}
printf("%d\n",ps);
for(int i=1;i<=ps;i++) printf("%lf %lf\n",v[stck[i]].first,v[stck[i]].second);
}