Pagini recente » Cod sursa (job #2179675) | Cod sursa (job #2667592) | Cod sursa (job #1680836) | Cod sursa (job #2073186) | Cod sursa (job #885444)
Cod sursa(job #885444)
#include<cstdio>
#include<list>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=120002;
const double oo = 1e-12;
int n,check[maxn],nre;
bool viz[maxn];
struct muchie{
float x,y;
};
muchie v[maxn];
void citire(){
int i;
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%f%f",&v[i].x,&v[i].y);
}
}
int compare(muchie A,muchie B){
return A.x<B.x || A.x<B.x && A.y<B.y;
}
double compara( muchie A, muchie B, muchie C){
return (C.y-A.y)*(B.x-A.x)-(B.y-A.y)*(C.x-A.x);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(v+1,v+n+1,compare);
check[1]=1;
check[2]=2;
nre=2;
for(int i=3;i<n;++i){
while(nre>2 && compara(v[nre-1],v[nre],v[i])<oo){
--nre;
}
++nre;
check[nre]=i;
}
printf("%d\n",nre+1);
for(int i=1;i<=nre;++i){
printf("%lf %lf\n",v[check[i]].x,v[check[i]].y);
}
printf("%lf %lf",v[n].x,v[n].y);
return 0;
}