Pagini recente » Cod sursa (job #746090) | Cod sursa (job #1860560) | Cod sursa (job #374687) | Cod sursa (job #2779682) | Cod sursa (job #708783)
Cod sursa(job #708783)
#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);
}
void infasuratoare() {
long i;
for(i=2;i<n;i++)
if(stiva[stivaSize-2].x*(stiva[stivaSize-1].y-punct[i].y)+stiva[stivaSize-1].x*(punct[i].y-stiva[stivaSize-2].y)+punct[i].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && stiva[stivaSize-3].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)+stiva[stivaSize-2].x*(stiva[stivaSize-1].y-stiva[stivaSize-3].y)+stiva[stivaSize-1].x*(stiva[stivaSize-3].y-stiva[stivaSize-2].y)<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
for(i=n-2;i>0;i--)
if(stiva[stivaSize-2].x*(stiva[stivaSize-1].y-punct[i].y)+stiva[stivaSize-1].x*(punct[i].y-stiva[stivaSize-2].y)+punct[i].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)>=0) {
stiva[stivaSize]=punct[i];
stivaSize++;
}
else {
stiva[stivaSize-1]=punct[i];
while(stivaSize>2 && stiva[stivaSize-3].x*(stiva[stivaSize-2].y-stiva[stivaSize-1].y)+stiva[stivaSize-2].x*(stiva[stivaSize-1].y-stiva[stivaSize-3].y)+stiva[stivaSize-1].x*(stiva[stivaSize-3].y-stiva[stivaSize-2].y)<0) {
stivaSize--;
stiva[stivaSize-1]=stiva[stivaSize];
}
}
}
int main() {
citeste(FI);
sort(0,n-1);
stiva[0]=punct[0];
stiva[1]=punct[1];
stivaSize=2;
infasuratoare();
scrie(FO);
return 0;
}