Pagini recente » Cod sursa (job #549793) | Cod sursa (job #494337) | Cod sursa (job #219576) | Cod sursa (job #2723236) | Cod sursa (job #560558)
Cod sursa(job #560558)
#include <cstdio>
#include <math.h>
struct punct{
double x,y,panta;
};
punct c[120006],c2[120006],s[120006];
int n,n2,ns;
void citire(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%lf %lf",&c[i].x,&c[i].y);
}
void detElemMin(){
int i,minimi;
punct minim,aux;
minim=c[1];
minimi=1;
for(i=2;i<=n;i++)
if(c[i].x<minim.x){
minim=c[i];
minimi=i;
}
else if(c[i].x==minim.x && c[i].y<minim.y){
minim=c[i];
minimi=i;
}
aux=c[1];
c[1]=c[minimi];
c[minimi]=aux;
}
void detPante(){
int i;
for(i=2;i<=n;i++){
if(c[i].x==c[1].x)
c[i].panta=2000000000;
else c[i].panta=(c[i].y-c[1].y)/(c[i].x-c[1].x);
}
}
int divide(int p,int q){
int st=p,dr=q;
punct aux=c[p];
while(st<dr){
while(st<dr && (c[dr].panta>aux.panta || (c[dr].panta==aux.panta && c[dr].x>aux.x) || (c[dr].panta==aux.panta && c[dr].x==aux.x && c[dr].y>=aux.y)))
dr--;
c[st]=c[dr];
while(st<dr && (c[st].panta<aux.panta || (c[st].panta==aux.panta && c[st].x<=aux.x)|| (c[st].panta==aux.panta && c[st].x==aux.x && c[st].y<=aux.y)))
st++;
c[dr]=c[st];
}
c[st]=aux;
return st;
}
void qSort(int p,int q){
int m=divide(p,q);
if(m-1>p)
qSort(p,m-1);
if(m+1<q)
qSort(m+1,q);
}
void initializareC2(){
int i;
n2=1;
c2[1]=c[1];
for(i=2;i<=n;i++){
n2++;
while(c[i].panta==c[i+1].panta){
i++;
}
c2[n2]=c[i];
}
}
double determinant(punct p1,punct p2,punct p3){
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p2.x*p1.y-p1.x*p3.y;
}
void rezolvare(){
detElemMin();
detPante();
qSort(2,n);
initializareC2();
int i;
s[1]=c2[1];
s[2]=c2[2];
s[3]=c2[3];
ns=3;
for(i=4;i<=n2;i++){
ns++;
s[ns]=c2[i];
while(determinant(s[ns-2],s[ns-1],s[ns])<0){
s[ns-1]=s[ns];
ns--;
}
}
}
void afisare(){
int i;
printf("%d\n",ns);
for(i=1;i<=ns;i++)
printf("%lf %lf\n",s[i].x,s[i].y);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
rezolvare();
afisare();
return 0;
}