Pagini recente » Cod sursa (job #399724) | Cod sursa (job #1949947) | Cod sursa (job #10607) | Cod sursa (job #432357) | Cod sursa (job #1883065)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 120005
using namespace std;
struct punct
{
double x,y;
}puncte[NMAX],stiva[NMAX];
int N,K;
void citire()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%lf%lf",&puncte[i].x,&puncte[i].y);
if(puncte[i].x<puncte[1].x)
swap(puncte[1],puncte[i]);
else if(puncte[i].x==puncte[1].x && puncte[i].y<puncte[1].y)
swap(puncte[1],puncte[i]);
}
}
double cross_prod(punct p1,punct p2,punct p3)
{
return (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);
}
bool comparare(punct p1,punct p2)
{
return cross_prod(puncte[1],p1,p2)>0;
}
void rezolvare()
{
sort(puncte+2,puncte+N+1 ,comparare);
stiva[++K]=puncte[1];
stiva[++K]=puncte[2];
for(int i=3;i<=N;i++)
{
while(K>=2 && cross_prod(stiva[K-1],stiva[K],puncte[i])<0)
K--;
stiva[++K]=puncte[i];
}
}
void afisare()
{
printf("%d\n",K);
for(int i=1;i<=K;i++)
printf("%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout );
citire();
rezolvare();
afisare();
return 0;
}