Pagini recente » Cod sursa (job #3183080) | Cod sursa (job #1435777) | Cod sursa (job #615519) | Cod sursa (job #462032) | Cod sursa (job #627170)
Cod sursa(job #627170)
#include <stdio.h>
#include <math.h>
#define INF 1000000010
struct nod{
double x,y;
}v[120005];
double panta[120005];
int convex[120005];//tine indicii punctelor care apar ca varfuri ale infasuratorii convexe
bool viz[120005];
int ppoz(int li,int ls){
int ii=1,jj=0;
double c;
nod aux;
while(li<ls){
if(panta[li]>panta[ls]){
c=panta[li];
panta[li]=panta[ls];
panta[ls]=c;
aux=v[li];
v[li]=v[ls];
v[ls]=aux;
c=ii;
ii=-jj;
jj=-c;
}
li+=ii;
ls+=jj;
}
return li;
}
void quick(int li,int ls){
int k;
if(li<ls){
k=ppoz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
bool e_convex(int vf){
//verific daca punctele care au indicii convex[vf-2], convex[vf-1] si convex[vf]
//fac un inghi mai mic de 180grade...
//verific asta facand determinantul triunghiului...
double xa=v[convex[vf-2]].x,ya=v[convex[vf-2]].y,xb=v[convex[vf-1]].x,yb=v[convex[vf-1]].y,xc=v[convex[vf]].x,yc=v[convex[vf]].y;
double aux1=(xa-xc)*(yb-yc),aux2=(xb-xc)*(ya-yc);//daca aux1-aux2 e pozitiv e bine
if(aux1>=aux2)return 1;
return 0;
}
int main(){
int n,i;
int ind;//indicele punctului celui mai din stanga, cel mai de jos
double xind=INF,yind=INF;
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
fscanf(fin,"%d",&n);
for(i=0;i<n;i++){
fscanf(fin,"%lf %lf",&v[i].x,&v[i].y);//long float, adica double
//printf("(%lf,%lf) \n",v[i].x,v[i].y);
if(v[i].x<xind){
ind=i;
xind=v[i].x;
yind=v[i].y;
}else if((v[i].x==xind)&&(v[i].y<yind)){ind=i;yind=v[i].y;}
}
fclose(fin);
//punctul ind este sigur pe infasuratoare, e un varf
//calculez panta tutor punctelor fata de acest punct ales
for(i=0;i<n;i++){
if(v[i].x!=xind){
panta[i]=(v[i].y-yind)/(v[i].x-xind);
}else{
//pt punctul ales panta va fi zero
if(v[i].y==yind){panta[i]=0;}
else if(v[i].y<yind)panta[i]=-INF;//asigur faptul ca punctul de pe aceeasi verticala cu punctul ales, dar dedesubt e primul ales
else panta[i]=INF;
}
}
//calculez si sortez descresc dupa panta
quick(0,n-1);
//dupa sortare nu mai stiu pe ce loc se afla (xind, yind)
for(i=0;i<n;i++)
if(v[i].x==xind && v[i].y==yind){ind=i;break;}
//printf("am ales punctul (%lf,%lf) de start\n",v[ind].x,v[ind].y);
//for(i=0;i<n;i++)printf("(%lf,%lf) ",v[i].x,v[i].y);
// printf("\n");
int vf=0;//indicele varfului stivei convex[]
//adaug primele doua puncte de mana...
convex[vf++]=ind;//primul este punctul ales
convex[vf++]=0;//al doilea este punctul cu panta cea mai mica fata de punctul dat
//vreau sa mai adaug un punct
i=1;//aici am ajuns in vector
do{
//verific punctul i
convex[vf]=i;
while(!e_convex(vf)){
vf--;
convex[vf]=i;
}
vf++;
i++;
}while(i<n);
//afisez convex
fprintf(fout,"%d\n",vf);
for(i=0;i<vf;i++)
fprintf(fout,"%lf %lf\n",v[convex[i]].x,v[convex[i]].y);
fclose(fout);
return 0;
}