Pagini recente » Cod sursa (job #1737738) | Cod sursa (job #3218932) | Cod sursa (job #2453672) | Cod sursa (job #2148136) | Cod sursa (job #1906869)
#include <stdio.h>
#include<algorithm>
using namespace std;
FILE *f,*g;
struct bla
{
float x; float y;
} date[120010];
int n,vf,used[120010];
int st[120010];
void read ()
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;i++)
fscanf(f,"%f %f",&date[i].x,&date[i].y);
}
bool sortare (bla q,bla w)
{
if(q.x==w.x) return q.y<w.y;
return q.x<w.x;
}
int ec_dreptei (int q,int w,int e)
{
bla a=date[q],b=date[w],c=date[e];
return (c.x-a.x)*(a.y-b.y)-(c.y-a.y)*(a.x-b.x);
}
void infasuratoare ()
{
sort(date+1,date+n+1,sortare);
int urm=3,dir=1; vf=2;
used[2]=1;
st[1]=1; st[2]=2;
while(used[1]==0)
{
while(used[urm]!=0)
{
if(urm==n) dir=-1;
urm+=dir;
}
while(vf>1 && ec_dreptei(st[vf-1],st[vf],urm)<0) used[st[vf--]]=0;
st[++vf]=urm;
used[urm]=1;
}
}
void write ()
{
fprintf(g,"%d\n",vf-1);
for(int i=1;i<vf;i++)
fprintf(g,"%f %f\n",date[st[i]].x,date[st[i]].y);
}
int main()
{
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
read();
infasuratoare();
write();
fclose(f);
fclose(g);
return 0;
}