Pagini recente » Cod sursa (job #1722164) | Cod sursa (job #1413238) | Cod sursa (job #812888) | Cod sursa (job #2071224) | Cod sursa (job #1097967)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double,double> punct;
punct Stiva[120001];
punct Sir[120001];
int N,k;
double Rotatie(const punct &A, const punct &B, const punct &C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool Cmp(const punct &A, const punct &B)
{
return Rotatie(Sir[1],A,B)<0;
}
void Citire()
{
int Poz=1;
scanf("%d",&N);
for(int i=1;i<=N;++i)
{
scanf("%lf %lf",&Sir[i].x,&Sir[i].y);
if(Sir[i]<Sir[Poz])
Poz=i;
}
swap(Sir[1],Sir[Poz]);
}
void Infasuratoare()
{
Stiva[1]=Sir[1];
Stiva[2]=Sir[2];
k=2;
for(int i=3;i<=N;++i)
{
while(k>=2 && Rotatie(Stiva[k-1],Stiva[k],Sir[i])>0)
k--;
Stiva[++k]=Sir[i];
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Citire();
sort(Sir+2,Sir+1+N,Cmp);
Infasuratoare();
printf("%d\n",k);
for(int i=k;i>=0;--i)
printf("%lf %lf\n",Stiva[i].x,Stiva[i].y);
return 0;
}