Pagini recente » Cod sursa (job #2506588) | Cod sursa (job #542089) | Cod sursa (job #2513742) | Cod sursa (job #1448237) | Cod sursa (job #270832)
Cod sursa(job #270832)
#include<stdio.h>
#include<algorithm>
#define PDD pair<double,double>
#define EPS 1e-12
using namespace std;
int n;
pair <double, double> nr[120010];
int st[120010];
double pantadr;
inline int cmp(double a,double b){
if(a+EPS<b)
return -1;
if(b+EPS<a)
return 1;
return 0;
}
int cmpp(const PDD &a,const PDD &b){
int r=cmp(a.first,b.first);
if(r!=0)
return r==-1;
return cmp(a.second,b.second)==-1;
}
int scot(int a,int b,int c){
double A=nr[a].second-nr[b].second,B=nr[b].first-nr[a].first,C=nr[a].first*nr[b].second-nr[b].first*nr[a].second;
return cmp(A*nr[c].first + B*nr[c].second + C,0);
}
double panta(int i){
double pp=(nr[i].second-nr[1].second)/(nr[i].first-nr[1].first);
return pp;
}
void inf(){
int i=2,vf=2;
st[1]=1;
st[2]=2;
while(i<=n){
++i;
if(panta(i)>pantadr)
continue;
while(vf>=2 && scot(st[vf-1],st[vf],i)==-1)
--vf;
st[++vf]=i;
}
i=n;
while(i>1){
--i;
if(panta(i)<pantadr)
continue;
while(vf>=2 && scot(st[vf-1],st[vf],i)==-1)
--vf;
st[++vf]=i;
}
printf("%d\n",vf-1);
for(i=1;i<vf;++i)
printf("%.6lf %.6lf\n",nr[st[i]].first,nr[st[i]].second);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&nr[i].first,&nr[i].second);
sort(nr+1,nr+n+1,cmpp);
pantadr=(nr[n].second-nr[1].second)/(nr[n].first-nr[1].first);
inf();
fclose(stdin);
fclose(stdout);
return 0;
}