Pagini recente » Cod sursa (job #475972) | Cod sursa (job #2729828) | Cod sursa (job #2784353) | Cod sursa (job #1288000) | Cod sursa (job #1142902)
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
struct Punct{
double x,y;
}P[120010];
bool cmp(Punct A,Punct B)
{
long double det = 1LL*(P[1].x*A.y + A.x*B.y + P[1].y*B.x - A.y*B.x - P[1].x*B.y - P[1].y*A.x);
return det>0;
}
bool trigo(int I,int J,int K)
{
long double det = 1LL*(P[I].x*P[J].y + P[J].x*P[K].y + P[I].y*P[K].x - P[J].y*P[K].x - P[I].x*P[K].y - P[I].y*P[J].x);
return det>0;
}
int ST[120010],head;
int i,n,pos;
double x,y;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf",&x,&y);
pos=1;
P[1].x=x;P[1].y=y;
for(i=2;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
if(P[pos].x==x && P[pos].y>y){ pos=i; }
if(P[pos].x>x){ pos=i; }
P[i].x=x;
P[i].y=y;
}
if(pos!=1)swap(P[pos],P[1]);
sort(P+2,P+n+1,cmp);
ST[1]=1;
ST[2]=2;
head=2;
for(i=3;i<=n;i++)
{
while(head>1)
{
if(trigo(ST[head-1],ST[head],i)==1)break;
head--;
}
ST[++head]=i;
}
printf("%d\n",head);
for(i=1;i<=head;i++)printf("%lf %lf\n",P[ST[i]].x,P[ST[i]].y);
}