Pagini recente » Cod sursa (job #3225651) | Cod sursa (job #1546967) | Cod sursa (job #230718) | Cod sursa (job #403541) | Cod sursa (job #1268298)
#include <stdio.h>
#define EPS 1e-12
#define MAXN 120000
#define INF 1000000000000000.0
int n, stiva[MAXN+1], ok[MAXN+1];
double x[MAXN], y[MAXN];
FILE *fout;
inline int tata(int a){
return (a-1)/2;
}
inline int fiust(int a){
return a*2+1;
}
inline int fiudr(int a){
return a*2+2;
}
inline void swap(int a, int b){
double aux=x[a];
x[a]=x[b];
x[b]=aux;
aux=y[a];
y[a]=y[b];
y[b]=aux;
}
inline int trbSchimb(int a, int b){
if(x[a]>x[b]){
return 1;
}
if((x[a]==x[b])&&(y[a]>=y[b])){
return 1;
}
return 0;
}
inline void coborare(int p){
int q, f;
f=1;
while((f==1)&&(fiust(p)<n)){
q=fiust(p);
if((fiudr(p)<n)&&(trbSchimb(fiudr(p), q)==1)){
q=fiudr(p);
}
if(trbSchimb(q, p)==1){
swap(p, q);
p=q;
}else{
f=0;
}
}
}
inline void heapify(){
int i;
for(i=tata(n-1); i>=0; i--){
coborare(i);
}
}
inline void heapSort(){
while(n>1){
n--;
swap(0, n);
coborare(0);
}
}
inline double modul(double a){
if(a>0){
return a;
}
return -a;
}
inline double crossProduct(int a, int b, int c){
return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]);
}
inline void convexHull(){
int vf, i, pas;
stiva[0]=0;
stiva[1]=1;
ok[1]=1;
vf=2;
pas=1;
for(i=2; i>=0; i+=pas){
if(i==n-1){
pas=-1;
}
if(ok[i]==0){
while((vf>=2)&&(crossProduct(stiva[vf-2], stiva[vf-1], i)<EPS)){
vf--;
ok[stiva[vf]]=0;
}
stiva[vf++]=i;
ok[i]=1;
}
}
vf--;
fprintf(fout, "%d\n", vf);
for(i=0; i<vf; i++){
fprintf(fout, "%.6lf %.6lf\n", x[stiva[i]], y[stiva[i]]);
}
}
int main(){
int i, cn;
FILE *fin;
fin=fopen("infasuratoare.in", "r");
fout=fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
for(i=0; i<n; i++){
fscanf(fin, "%lf%lf", &x[i], &y[i]);
}
heapify();
cn=n;
heapSort();
n=cn;
convexHull();
fclose(fin);
fclose(fout);
return 0;
}