Pagini recente » Cod sursa (job #347827) | Cod sursa (job #1633917) | Cod sursa (job #27825) | Cod sursa (job #2562807) | Cod sursa (job #709224)
Cod sursa(job #709224)
/*******************
*N/A - O(N log2 N)*
*******************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxN 120001
#define Error 1
using namespace std;
struct punct
{
double x,y;
}P[maxN];
int use[maxN],st[maxN];
inline bool cmp(punct a,punct b)
{
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
inline int unghi(punct a,punct b,punct c)
{
return (b.x-a.x)*(c.y-a.y)+Error<(c.x-a.x)*(b.y-a.y);
}
int main()
{
int N;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&N);
for(int i=1;i<=N;++i)
scanf("%lf%lf",&P[i].x,&P[i].y);
sort(P+1,P+N+1,cmp);
memset(use,0,sizeof(use));
use[1]=1;
use[2]=1;
st[0]=2;
st[1]=1;
st[2]=2;
for(int i=3;i<=N;++i)
if(!use[i])
{
while(unghi(P[st[st[0]-1]],P[st[st[0]]],P[i])) use[st[st[0]--]]=0;
st[++st[0]]=i;
use[i]=1;
}
for(int i=N-1;i>1;--i)
if(!use[i])
{
while(unghi(P[st[st[0]-1]],P[st[st[0]]],P[i])) use[st[st[0]--]]=0;
st[++st[0]]=i;
use[i]=1;
}
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;
}