Pagini recente » Cod sursa (job #718987) | Cod sursa (job #1638047) | Cod sursa (job #549220) | Cod sursa (job #2325250) | Cod sursa (job #1675190)
#include <stdio.h>
#include <algorithm>
#define lim 120005
#define maxim 1000000005
using namespace std;
int st[lim];
struct elem{float x,y;};
elem v[lim];
int tg(elem a,elem b,elem c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(elem a,elem b){
return tg(v[1],a,b)<0;
}
int main(){
FILE *fin,*fout;
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w");
int i,n,k=0;
fscanf(fin,"%d",&n);
v[k].x=maxim;
v[k].y=maxim;
for(i=1;i<=n;i++){
fscanf(fin,"%f%f",&v[i].x,&v[i].y);
if(v[i].x==v[k].x&&v[i].y<v[k].y)
k=i;
if(v[i].x<v[k].x)
k=i;
}
v[n+1]=v[1];
v[1]=v[k];
v[k]=v[n+1];
sort(v+2,v+n+1,cmp);
st[1]=1;
st[2]=2;
k=2;
for(i=3;i<=n;i++){
while(k>=3&&tg(v[st[k-1]],v[st[k]],v[i])>0)
k--;
k++;
st[k]=i;
}
fprintf(fout,"%d\n",k);
for(i=k;i>=1;i--)
fprintf(fout,"%0.6f %0.6f\n",v[st[i]].x,v[st[i]].y);
fclose(fin);
fclose(fout);
return 0;
}