Pagini recente » Cod sursa (job #118358) | Cod sursa (job #871663) | Cod sursa (job #2778368) | Cod sursa (job #3218264) | Cod sursa (job #878316)
Cod sursa(job #878316)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define er 0.0000000000001
#define nmax 120005
using namespace std;
double x[nmax],y[nmax];
int poz[nmax],n,s[nmax],vf;
double det(int i,int j,int k){
return x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-y[j]*x[k]-y[k]*x[i]-y[i]*x[j];
}
int cmp(int i,int j){
return (y[i]-y[poz[0]])*(x[j]-x[poz[0]])<(x[i]-x[poz[0]])*(y[j]-y[poz[0]]);
}
void cit(){
FILE *f;
int i;
f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
fscanf(f,"%lf%lf",&x[1],&y[1]);
poz[0]=1;
for(i=2;i<=n;i++){
fscanf(f,"%lf%lf",&x[i],&y[i]);
if(x[i]<x[poz[0]]||(x[i]==x[poz[0]]&&y[i]<y[poz[0]]))
poz[0]=i;
}
for(i=1;i<poz[0];i++)
poz[i]=i;
for(i=poz[0]+1;i<=n;i++)
poz[i-1]=i;
fclose(f);
}
int main(){
cit();
sort(poz+1,poz+n,cmp);
for(int i=0;i<n;i++)
printf("%lf %lf\n",x[poz[i]],y[poz[i]]);
vf=2;
s[1]=poz[0];
s[2]=poz[1];
for(int i=2;i<n;i++){
while(vf>=2&&det(s[vf-1],s[vf],poz[i])<=0)
vf--;
vf++;
s[vf]=poz[i];
}
FILE *f;
f=fopen("infasuratoare.out","w");
fprintf(f,"%d\n",vf);
for(int i=1;i<=vf;i++)
fprintf(f,"%lf %lf\n",x[s[i]],y[s[i]]);
fclose(f);
return 0;
}