Pagini recente » Cod sursa (job #573741) | Cod sursa (job #2731504) | Cod sursa (job #81235) | Cod sursa (job #1891814) | Cod sursa (job #1638700)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define pi 3.14159265
using namespace std;
int n,q,nr=2,s[120001];
struct punct
{
double/*float*/ x,y,tg;
} a[120001];
void cit()
{
scanf("%d ",&n);
int i;
for(i=1; i<=n; ++i)
scanf("%lf %lf ",&a[i].x,&a[i].y);
}
void afis()
{
printf("%d\n",nr);
int i;
for(i=1; i<=nr; ++i)
printf("%f %f\n",a[s[i]].x,a[s[i]].y);
}
void aleg()
{
int i;
double/*float*/ miny=1000000000,minx=1000000000;
for(i=1; i<=n; ++i)
{
if(miny>a[i].y)
{
miny=a[i].y;
minx=a[i].x;
q=i;
}
else if(miny==a[i].y&&minx>a[i].x)
{
minx=a[i].x;
q=i;
}
}
//printf("%d\n",q); //
}
inline bool comp(punct i, punct j)
{
if(i.tg<0&&j.tg>=0) return 0;
if(i.tg>=0&&j.tg<0) return 1;
if(i.tg!=j.tg) return(i.tg<j.tg);
else return (sqrt((i.y-a[q].y)*(i.y-a[q].y)+(i.x-a[q].x)*(i.x-a[q].x))<sqrt((j.y-a[q].y)*(j.y-a[q].y)+(j.x-a[q].x)*(j.x-a[q].x)));
}
void arctang()
{
int i;
for(i=1; i<=n; ++i)
{
if(i!=q)
//{
/*if(a[i].x!=a[q].x)*/
{
a[i].tg=atan((a[i].y-a[q].y)/(a[i].x-a[q].x))*180/pi;
if(a[i].tg<0) a[i].tg=180+a[i].tg;
}
else a[i].tg=0;
//}
//else a[i].tg=0;
printf("%f\n",a[i].tg); //
}
sort(a+1,a+n+1,comp);
}
inline bool ok(int p0, int p1, int p2)
{
return(((a[p1].x-a[p0].x)*(a[p2].y-a[p0].y)-(a[p2].x-a[p0].x)*(a[p1].y-a[p0].y))>=0);
}
void generare()
{
int i/*,p1=1,p2=2,p=1*/;
for(i=3; i<=n; ++i)
{
if(ok(/*p1,p2,*/s[nr-1],s[nr],i))
{
/*p=p1;
p1=p2;
p2=i;*/
s[++nr]=i;
}
else
{
//p2=p1;
//p1=p;
//--i;
--nr;
while(!ok(s[nr-1],s[nr],i))
{
--nr;
}
s[++nr]=i;
}
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cit();
aleg();
arctang();
s[1]=1;
s[2]=2;
generare();
afis();
return 0;
}