Pagini recente » Cod sursa (job #179879) | Cod sursa (job #1337057) | Cod sursa (job #2542244) | Cod sursa (job #1410698) | Cod sursa (job #709235)
Cod sursa(job #709235)
/*******************
*N/A - O(N log2 N)*
*******************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxN 120001
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)<=(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(st[0]>1&&unghi(P[st[st[0]-1]],P[st[st[0]]],P[i])) use[st[st[0]--]]=0;
st[++st[0]]=i;
use[i]=1;
}
use[1]=0;
for(int i=N-1;i>0;--i)
if(!use[i])
{
while(st[0]>1&&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]-1);
for(int i=1;i<st[0];++i)
printf("%.7lf %.7lf\n",P[st[i]].x,P[st[i]].y);
return 0;
}