Pagini recente » Cod sursa (job #1317305) | Cod sursa (job #1678284) | Cod sursa (job #2682058) | Cod sursa (job #1753755) | Cod sursa (job #1111257)
#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double,double> Point;
const int NMAX = 120000+2;
int N;
int S[NMAX],top;
Point V[NMAX];
inline double CrossProduct(Point A,Point B,Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline bool cmp(Point A,Point B)
{
return CrossProduct(V[1],A,B)<0;
}
int main()
{
int i,p=1;
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",&V[i].x,&V[i].y);
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,cmp);
//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++)
{
while(CrossProduct(V[S[top-1]],V[S[top]],V[i])>0 && top>=2) top--;
S[++top]=i;
}
//Afisam solutia
printf("%d\n",top);
for(i=top; i>=1; i--)
printf("%lf %lf\n",V[S[i]].x,V[S[i]].y);
return 0;
}