Pagini recente » Cod sursa (job #1100697) | Cod sursa (job #2918225) | Cod sursa (job #34287) | Cod sursa (job #2591827) | Cod sursa (job #2211422)
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
FILE *in,*out;
int n;
bool used[120002];
int st[120002];
struct name{
double x,y;
}v[120002];
bool how (name a, name b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
void read(){
fscanf(in,"%d",&n);
for(int i=1;i<=n;i++)
fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,how);
}
double determinant (name a, name b, name c){
return ((a.x*b.y+b.x*c.y+c.x*a.y)-(b.y*c.x+c.y*a.x+a.y*b.x));
}
int main(){
in=fopen("infasuratoare.in","r");
out=fopen("infasuratoare.out","w");
read();
int vf=2,poz=3,ok=1;
st[1]=1,st[2]=2;
used[2]=1;
while(!used[1]){
while(used[poz]){
if(poz==n)
ok=-1;
poz+=ok;
}
while(vf>=2 && determinant(v[st[vf-1]],v[st[vf]],v[poz])<0){
used[st[vf]]=0;
vf--;
}
vf++;
st[vf]=poz;
used[poz]=1;
}
fprintf(out,"%d\n",vf-1);
for(int i=2;i<=vf;i++)
fprintf(out,"%6f %6f\n",v[st[i]].x,v[st[i]].y);
return 0;
}