Pagini recente » Cod sursa (job #2496553) | Cod sursa (job #2453159) | Cod sursa (job #2801941) | Cod sursa (job #1870637) | Cod sursa (job #383967)
Cod sursa(job #383967)
using namespace std;
#include <cstdio>
#include <algorithm>
#define NN 120005
struct punct{
double x,y;
};
int n, nS;
punct v[NN], S[NN];
void citire(){
freopen("infasuratoare.in","r",stdin);
scanf("%d", &n);
for(int i=0;i<n;i++)
scanf("%lf%lf", &v[i].x, & v[i].y);
}
void primulPunct(){
int poz=0;
for(int i=1;i<n;++i)
if(v[i].x<v[poz].x)
poz = i;
else
if(v[i].x==v[poz].x && v[i].y<v[poz].y)
poz = i;
punct aux=v[0];v[0]=v[poz];v[poz]=aux;
}
void afisare(punct a[], int n,int dep=0){
for(int i=dep;i<n+dep;++i)
printf("%.6lf %.6lf\n",a[i].x,a[i].y);
}
int directie(punct A, punct B, punct C){
double d=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
if(d==0)
return 0; //inainte
if(d<0)
return -1; //dreapta
return 1;//stanga
}
int fcmp(punct A, punct B){
if (directie(v[0],A,B)>0)
return 1;
if(directie(v[0],A,B)<0)
return 0;
return (v[0].x-A.x)*(v[0].x-A.x)+(v[0].y-A.y)*(v[0].y-A.y)
<
(v[0].x-B.x)*(v[0].x-B.x)+(v[0].y-B.y)*(v[0].y-B.y);
}
void sortare(){
sort(v+1,v+n,fcmp);
}
void graham(){
nS=0;
S[++nS]=v[0];
S[++nS]=v[1];
for(int i=2;i<n;++i){
while(directie(S[nS-1],S[nS],v[i])<=0 && nS>1)
nS--;
S[++nS]=v[i];
}
}
int main(){
citire();
primulPunct();
sortare();
graham();
//afisare(v,n);
//printf("\n");
freopen("infasuratoare.out","w",stdout);
printf("%d\n",nS);
afisare(S,nS,1);
return 0;
}