Pagini recente » Cod sursa (job #2281647) | Cod sursa (job #1585452) | Cod sursa (job #663482) | Cod sursa (job #2975033) | Cod sursa (job #727772)
Cod sursa(job #727772)
#include<stdio.h>
#include<algorithm>
#define nmax 120005
using namespace std;
int n,poz[nmax],s[nmax],vf;
double x[nmax],y[nmax];
//||((y[i]-y[0])*(x[j]-x[0])>(y[j]-y[0])*(x[i]-x[0])&&dist(0,i)<dist(0,j))
int cmp(int i,int j){
return (y[i]-y[0])*(x[j]-x[0])<(y[j]-y[0])*(x[i]-x[0]);
}
double det(int i,int j,int k){
return x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-x[k]*y[j]-x[j]*y[i]-x[i]*y[k];
}
void cit(){
FILE *f;
int i;
f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
x[0]=y[0]=(double)2000000000;
for(i=1;i<=n;i++){
fscanf(f,"%lf%lf",&x[i],&y[i]);
if(x[i]<x[0]||(x[i]==x[0]&&y[i]<y[0])){
x[0]=x[i];
y[0]=y[i];
poz[0]=i;
}
}
x[0]=x[poz[0]];
y[0]=y[poz[0]];
poz[0]=0;
for(i=1;i<poz[0];i++)
poz[i]=i;
for(i=poz[0]+1;i<=n;i++){
x[i-1]=x[i];
y[i-1]=y[i];
poz[i-1]=i-1;
}
fclose(f);
}
void afis(){
int i;
FILE *f;
f=fopen("infasuratoare.out","w");
fprintf(f,"%d\n",vf);
for(i=1;i<=vf;i++)
fprintf(f,"%lf %lf\n",x[s[i]],y[s[i]]);
fclose(f);
}
int main(){
cit();
sort(poz+1,poz+n,cmp);
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];
}
afis();
return 0;
}