Pagini recente » Cod sursa (job #1312586) | Cod sursa (job #420297) | Cod sursa (job #2615177) | Cod sursa (job #541964) | Cod sursa (job #264454)
Cod sursa(job #264454)
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <list>
using namespace std;
double x[120001];
double y[120001];
double cs[120001];
int id[120001];
void sort(int st,int dr)
{int s=st,d=dr,aux;
double p=cs[id[st+rand()%(dr-st+1)]];
while(s<d)
{while(cs[id[s]]>p)s++;
while(cs[id[d]]<p)d--;
if(s<=d)
{aux=id[s];id[s]=id[d];id[d]=aux;
s++;
d--;
}
}
if(st<d)
sort(st,d);
if(s<dr)
sort(s,dr);
}
int test(list<int> l)
{list<int>::iterator it1,it2,it3;
it1=--l.end();
it2=----l.end();
it3=------l.end();
return ((y[*it1]-y[*it2])*(x[*it3]-x[*it2])-(y[*it3]-y[*it2])*(x[*it1]-x[*it2]))>0.0;
}
int main ()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,p,i;
double y1,x1;
list<int> l;
list<int>::reverse_iterator itr;
list<int>::iterator it;
scanf("%d",&n);
for (i=1,p=0,y1=1000000002.0;i<=n;i++)
{ scanf("%lf%lf",&x[i],&y[i]);
if(y[i]<y1)
{p=i;
y1=y[i];
}
}
x1=x[p];
x[p]=x[n];
y[p]=y[n];
n--;
for (i=1;i<=n;i++)
{cs[i]=(x[i]-x1)/sqrt((x[i]-x1)*(x[i]-x1)+(y[i]-y1)*(y[i]-y1));}
for (i=1;i<=n;i++)
id[i]=i;
sort(1,n);
for (i=1;i<=n;i++)
{while(l.size()>2&&test(l))
{it=l.end();
it--;it--;
l.erase(it);
}
l.push_back(id[i]);
}
printf("%d\n",l.size()+1);
printf("%lf %lf\n",x1,y1);
for (it=l.begin();it!=l.end();it++)
printf("%lf %lf\n",x[*it],y[*it]);
return 0;
}