Pagini recente » Cod sursa (job #312705) | Cod sursa (job #1298727) | Cod sursa (job #2610279) | Cod sursa (job #2249359) | Cod sursa (job #1432584)
#include <stdio.h>
#include <math.h>
#define EPS 0.0000000000001
#define INF 2000000000.0
#define MAXN 120000
typedef struct{
double x, y;
}punct;
punct v[MAXN];
int n, vf, st[MAXN];
double bashtanu, barosanu;
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-bashtanu)>atan2(v[a].y-barosanu, v[a].x-bashtanu));
}
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 double arie(punct a, punct b, punct c){
return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}
inline void convexHull(){
int i;
st[0]=n;
st[1]=0;
st[2]=1;
vf=3;
for(i=2; i<n; i++){
while((vf>2)&&(arie(v[i], v[st[vf-1]], v[st[vf-2]])>0)){
vf--;
}
st[vf++]=i;
}
}
inline double myabs(double x){
if(x<0){
return -x;
}
return x;
}
int main(){
int i, sefu;
FILE *fin, *fout;
fin=fopen("infasuratoare.in", "r");
fout=fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
sefu=0;
for(i=0; i<n; i++){
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
if(((myabs(v[i].y-v[sefu].x)<EPS)&&(v[sefu].x>v[sefu].y))||(v[sefu].y>v[i].y)){
sefu=i;
}
}
swap(n-1, sefu);
n--;
bashtanu=v[n].x;
barosanu=v[n].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;
}