Pagini recente » Cod sursa (job #3135288) | Cod sursa (job #2637298) | Cod sursa (job #1386000) | Cod sursa (job #2507917) | Cod sursa (job #705758)
Cod sursa(job #705758)
/******************************
*Scanarea Graham - O(N log2 N)*
******************************/
#include <stdio.h>
#include <algorithm>
#define maxN 120001
using namespace std;
struct punct
{
double x,y;
}P[maxN],pi;
int St[maxN];
int N;
inline bool cmp(punct a,punct b)
{
return (a.x-pi.x)*(b.y-pi.y)>(b.x-pi.x)*(a.y-pi.y);
}
inline int turn(punct a,punct b,punct c)
{
return (a.x-c.x)*(b.y-c.y)<(a.y-c.y)*(b.x-c.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&N);
for(int i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);
pi=P[1];
int pos=1;
for(int i=2;i<=N;++i)
if(pi.x>P[i].x) pi=P[i], pos=i;
else
if(pi.x==P[i].x&&pi.y>P[i].y) pi=P[i], pos=i;
pi=P[1];
P[1]=P[pos];
P[pos]=pi;
pi=P[1];
sort(P+2,P+N+1,cmp);
St[0]=2;
St[1]=1;
St[2]=2;
for(int i=3;i<=N;++i)
{
while(turn(P[St[St[0]-1]],P[St[St[0]]],P[i])) --St[0];
St[++St[0]]=i;
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",St[0]);
for(int i=1;i<=St[0];++i)
printf("%.7lf %.7lf\n",P[St[i]].x,P[St[i]].y);
return 0;
}