Pagini recente » Cod sursa (job #84607) | Cod sursa (job #1968757) | Cod sursa (job #2680350) | Cod sursa (job #1168213) | Cod sursa (job #411255)
Cod sursa(job #411255)
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define MaxN 120024
#define prec 0.000000000001
struct punct{
double x,y,cos;
} P[MaxN],P2[MaxN];
int N,M;
int s[MaxN];
int cmp(punct A,punct B)
{
return (A.cos-B.cos>prec || (fabs(A.cos-B.cos)<prec && B.x-A.x>prec) || (fabs(A.cos-B.cos)<prec && fabs(A.x-B.x)<prec && A.y-B.y>prec));
}
void read()
{
int i,poz;
punct aux;
double minx,miny;
scanf("%d",&N);
scanf("%lf%lf",&P[1].x,&P[1].y);
minx=P[1].x; miny=P[1].y; poz=1;
for(i=2;i<=N;i++)
{
scanf("%lf%lf",&P[i].x,&P[i].y);
if(P[i].y<miny || (P[i].y==miny && P[i].x<minx))
{
minx=P[i].x; miny=P[i].y;
poz=i;
}
}
aux=P[1]; P[1]=P[poz]; P[poz]=aux;
}
double dist(punct A,punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
void cosinus()
{
int i;
for(i=2;i<=N;i++)
P[i].cos=(P[i].x-P[1].x)/dist(P[i],P[1]);
std::sort(P+2,P+N+1,cmp);
}
double determinant(punct P1,punct P2,punct P3)
{
return P1.x*P2.y+P1.y*P3.x+P2.x*P3.y-P3.x*P2.y-P3.y*P1.x-P2.x*P1.y;
}
void dreapta(punct A,punct B,double &a,double &b,double &c)
{
a=A.y-B.y;
b=B.x-A.x;
c=A.x*B.y-B.x*A.y;
}
void elimina_coliniar()
{
int i,j,k,n=1;
double a,b,c;
i=2;
P2[1]=P[1];
while(i<=N)
{
dreapta(P2[n],P[i],a,b,c);
k=i;
while(fabs(a*P[k].x+b*P[k].y+c)<0.0001 && k<=N)
k++;
i=k;
P2[++n]=P[k-1];
}
N=n;
}
void solve()
{
cosinus();
elimina_coliniar();
int i;
double det;
M=2; s[1]=1; s[2]=2;
for(i=3;i<=N;i++)
{
det=determinant(P2[s[M-1]],P2[s[M]],P2[i]);
while(det<0 && M>2)
{
M--;
det=determinant(P2[s[M-1]],P2[s[M]],P2[i]);
}
s[++M]=i;
}
}
void write()
{
int i;
printf("%d\n",M);
for(i=1;i<=M;i++)
printf("%lf %lf\n",P2[s[i]].x,P2[s[i]].y);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}