Pagini recente » Cod sursa (job #1810969) | Cod sursa (job #1010218) | Cod sursa (job #1482952) | Cod sursa (job #2237484) | Cod sursa (job #2310714)
#include <stdio.h>
#define NMAX 120002
#include <bitset>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct bla
{
double x,y;
}v[NMAX];
int s[NMAX];
bitset <NMAX> viz;
bool how(bla A, bla B)
{
if(A.x==B.x)
return A.y<B.y;
return A.x<B.x;
}
double determinant(bla A, bla B, bla C)
{
double a=A.x,b=A.y,c=B.x,d=B.y,e=C.x,f=C.y;
double delta=a*d+c*f+e*b-d*e-a*f-c*b;
return delta;
}
void make(int n, int &top)
{
int ok=1,i;
s[1]=1;
s[2]=2,viz[2]=1;
top=2;
i=3;
while(!viz[1])
{
while(viz[i])
{
if(i==n) ok=-1;
i+=ok;
}
while(determinant(v[s[top-1]],v[s[top]],v[i])<0 && top>=2)
viz[s[top]]=0,--top;
///delta=0, punctele sunt coliniare
///delta<0, punctele constituie o orientare in sensul invers acelor de ceasornic
///sens trigonometric
///delta>0, punctele constituie o orientare in sensul acelor de ceasornic
s[++top]=i;
viz[i]=1;
}
--top;
}
int main()
{
int top;
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
int n;
fscanf(f,"%d",&n);
for(int i=1;i<=n;++i)
fscanf(f,"%lf %lf",&v[i].x, &v[i].y);
sort(v+1,v+n+1,how);
make(n,top);
fprintf(f,"%d\n",top);
for(int i=2;i<=top+1;++i)
fprintf(g,"%lf %lf\n",v[s[i]].x,v[s[i]].y);
fclose(f);
fclose(g);
return 0;
}