Pagini recente » Cod sursa (job #2563607) | Cod sursa (job #2965097) | Cod sursa (job #145761) | Cod sursa (job #2318329) | Cod sursa (job #1785568)
#include <iostream>
#include <algorithm>
#include <cstdio>
#define NMAX 120005
using namespace std;
struct punct
{
double x,y;
};
int N,K;
punct puncte[NMAX];
punct stiva[NMAX];
void citire()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%lf%lf",&puncte[i].x,&puncte[i].y);
if(puncte[1].x > puncte[i].x)
swap(puncte[1],puncte[i]);
else if(puncte[1].x == puncte[i].x && puncte[1].y > puncte[i].y)
swap(puncte[1],puncte[i]);
}
}
double cross_product(punct a,punct b,punct c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
bool comp(punct a,punct b)
{
return cross_product(puncte[1],a,b)>0;
}
void infasuratoare()
{
stiva[++K] = puncte[1];
stiva[++K] = puncte[2];
for(int i=3;i<=N;i++)
{
while(K>=2 && cross_product(stiva[K-1],stiva[K],puncte[i])<0)
K--;
stiva[++K] = puncte[i];
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(puncte+2,puncte+N+1,comp);
infasuratoare();
for(int i=1;i<=K;i++)
printf("%lf %lf\n",stiva[i].x,stiva[i].y);
return 0;
}