Pagini recente » Cod sursa (job #1503545) | Cod sursa (job #1084913) | Cod sursa (job #940108) | Cod sursa (job #676536) | Cod sursa (job #1432238)
#include <stdio.h>
#include <math.h>
#define INF 2000000000.0
#define MAXN 120000
typedef struct{
double x, y;
}punct;
punct v[MAXN];
int n, vf, sefu, barosanu, st[MAXN];
inline int tata(int p){
return (p-1)/2;
}
inline int fiust(int p){
return 2*p+1;
}
inline int fiudr(int p){
return 2*p+2;
}
inline int cmp(int a, int b){
return (atan2(v[b].y-barosanu, v[b].x-sefu)>atan2(v[a].y-barosanu, v[a].x-sefu));
}
inline void swap(int a, int b){
punct aux=v[a];
v[a]=v[b];
v[b]=aux;
}
inline void coborare(int p){
int q, f=1;
while((f==1)&&(fiust(p)<n)){
q=fiust(p);
if((fiudr(p)<n)&&(cmp(q, fiudr(p)))){
q=fiudr(p);
}
if(cmp(p, q)){
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(){
int cn=n;
while(n>1){
n--;
swap(0, n);
coborare(0);
}
n=cn;
}
inline int arie(punct a, punct b, punct c){
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
inline void convexHull(){
int i;
st[0]=0;
st[1]=1;
st[2]=2;
vf=3;
for(i=3; i<n; i++){
while((vf>2)&&(arie(v[i], v[st[vf-1]], v[st[vf-2]])>0)){
vf--;
}
st[vf++]=i;
}
}
int main(){
int i;
FILE *fin, *fout;
fin=fopen("infasuratoare.in", "r");
fout=fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
sefu=barosanu=INF;
for(i=0; i<n; i++){
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
if(barosanu>v[i].y){
sefu=v[i].x;
barosanu=v[i].y;
}
}
heapify();
heapSort();
convexHull();
fprintf(fout, "%d\n", vf);
for(i=0; i<vf; i++){
fprintf(fout, "%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
}
fclose(fin);
fclose(fout);
return 0;
}