Pagini recente » Cod sursa (job #871838) | Cod sursa (job #1888109) | Cod sursa (job #2487318) | Rating Ecaterina Minca (catiminca11) | Cod sursa (job #1042672)
#include<cstdio>
#include<algorithm>
#include<utility>
#define NMAX 120000+5
#define PDD pair<double,double>
#define x first
#define y second
using namespace std;
int N,top;
PDD V[NMAX];
PDD ST[NMAX];
inline double crossproduct(PDD A,PDD B,PDD C){return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);}
inline bool crit(PDD A,PDD B){return crossproduct(V[1],A,B)<0;}
int main()
{
int i,p=1;
double a,b;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
//1. Alegem un punct extrem (cel mai din stanga) care cu
//siguranta face parte din infasuratoare
for(i=1;i<=N;i++)
{
scanf("%lf%lf",&a,&b);
V[i]=make_pair(a,b);
if(V[i]<V[p]) p=i;
}
//2. Sortam punctele dupa unghiul polar pe care il fac
//cu punctul P selectat
swap(V[1],V[p]);
sort(V+2,V+N+1,crit);
//3. Analizam tripletele de puncte consecutive Pi,Pi+1,
//Pi+2. Daca face intoarcere la dreapta, atunci Pi+1 nu
//poate face parte din infasuratoare
for(i=1;i<=N;i++)
{
for(;top>=2 && crossproduct(ST[top-1],ST[top],V[i])>0;top--);
ST[++top]=V[i];
}
//Afisam solutia
printf("%d\n",top);
for(i=top;i>=1;i--) printf("%lf %lf\n",ST[i].x,ST[i].y);
return 0;
}