Pagini recente » Cod sursa (job #305648) | Cod sursa (job #1032195) | Cod sursa (job #804388) | Cod sursa (job #256288) | Cod sursa (job #724347)
Cod sursa(job #724347)
#include <stdio.h>
#include <math.h>
#define FI fopen("infasuratoare.in","r")
#define FO fopen("infasuratoare.out","w")
struct Punct {
double x,y;
} punct[120000],stiva[120000];
long n,stivaSize;
void citeste(FILE *f) {
long i;
fscanf(f,"%li",&n);
for(i=0;i<n;i++)
fscanf(f,"%lf%lf",&punct[i].x,&punct[i].y);
}
void scrie(FILE *f) {
long i;
fprintf(f,"%li\n",stivaSize);
for(i=0;i<stivaSize;i++)
fprintf(f,"%lf %lf\n",stiva[i].x,stiva[i].y);
}
int compare(Punct a, Punct b) {
if(a.x<b.x)
return 1;
if(a.x>b.x)
return 0;
if(a.y<b.y)
return 1;
return 0;
}
void schimba(Punct &a, Punct &b) { Punct aux=a;a=b;b=aux; }
void sort(long li,long ls) {
long i,j;
if(li>=ls) return;
for(i=li+1,j=li+1;i<=ls;i++)
if(compare(punct[i],punct[li]))
schimba(punct[i],punct[j++]);
schimba(punct[li],punct[j-1]);
sort(li,j-2);
sort(j,ls);
}
double produs(Punct a,Punct b,Punct c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
void infasuratoare() {
long i;
for(i=2;i<n;i++)
if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
for(i=n-2;i>=0;i--)
if(produs(stiva[stivaSize-2],stiva[stivaSize-1],punct[i])>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && produs(stiva[stivaSize-3],stiva[stivaSize-2],stiva[stivaSize-1])<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
stivaSize--;
}
int main() {
citeste(FI);
sort(0,n-1);
stiva[0]=punct[0];
stiva[1]=punct[1];
stivaSize=2;
infasuratoare();
scrie(FO);
return 0;
}