Pagini recente » Cod sursa (job #1992834) | Cod sursa (job #1926224) | Cod sursa (job #2843687) | Cod sursa (job #1123109) | Cod sursa (job #2571373)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1.0e-12;
const int NMAX=120005,INF=2000000000;
struct POINT
{
double x,y,unghi;
};
POINT P[NMAX],st[NMAX];
double rad_to_grad(double x)
{
double u;
u=(180*x)/M_PI;
return u;
}
double unghi_3_puncte(POINT A,POINT O,POINT B)
{
double dif,unghi;
dif=fabs(atan2(A.y-O.y,A.x-O.x)-atan2(B.y-O.y,B.x-O.x));
if(dif-M_PI>=eps)
dif=2*M_PI-dif;
unghi=rad_to_grad(dif);
return unghi;
}
bool cmp(POINT P1,POINT P2)
{
if(P1.unghi==P2.unghi && P1.x==P2.x)
return (P1.y>P2.y);
if(P1.unghi==P2.unghi)
return (P1.x>P2.x);
return (P1.unghi<P2.unghi);
}
double cp(POINT P1,POINT P2,POINT P3)
{
return ((P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x));
}
int ccw(POINT P1,POINT P2,POINT P3)
{
double val_cp;
val_cp=cp(P1,P2,P3);
if(fabs(val_cp)<eps)
return 0;
if(val_cp>=eps)
return 1;
return -1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,ind0,top;
double tempx,tempy;
POINT P0,A,O,B;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&tempx,&tempy);
P[i].x=tempx;
P[i].y=tempy;
}
P0.x=INF;
P0.y=INF;
for(i=1;i<=n;i++)
{
if(P[i].y-P0.y<=-eps || (fabs(P[i].y-P0.y)<eps && P[i].x-P0.x<=-eps))
{
P0=P[i];
ind0=i;
}
}
for(i=ind0+1;i<=n;i++)
P[i-1]=P[i];
O=P0;
B.x=O.x+1;
B.y=O.y;
for(i=1;i<n;i++)
{
A=P[i];
P[i].unghi=unghi_3_puncte(A,O,B);
}
sort(P+1,P+n,cmp);
top=0;
st[++top]=P0;
st[++top]=P[1];
st[++top]=P[2];
for(i=3;i<n;i++)
{
if(fabs(P[i].unghi-P[i-1].unghi)>=eps)
{
while(ccw(st[top-1],st[top],P[i])==-1)
top--;
st[++top]=P[i];
}
}
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%lf %lf\n",st[i].x,st[i].y);
fclose(stdin);
fclose(stdout);
return 0;
}