Cod sursa(job #1242239)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 octombrie 2014 09:30:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define PDD pair < double , double >
#define NMAX 120500
#define F first
#define S second

PDD P[NMAX];
int _i,i,N,f;
int Q[NMAX];

double w(PDD A,PDD B,PDD C)
{
     return (A.F-C.F)*(B.S-C.S)-(B.F-C.F)*(A.S-C.S);
}

bool compare(PDD A,PDD B)
{
    return (w(P[1],A,B)>0);
}

int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);

for (i=_i=1,scanf("%d",&N);i<=N;++i)
{
    scanf("%lf%lf",&P[i].F,&P[i].S);
    if (P[i]<P[_i]) _i=i;
}

swap(P[1],P[_i]);
sort(P+2,P+N+1,compare);

Q[1]=1,Q[2]=f=2;

for (i=3;i<=N;++i)
{
    while (f>=2 && w(P[Q[f]],P[Q[f-1]],P[i])>=0)
    --f;

    Q[++f]=i;
}

printf("%d\n",f);

for (i=1;i<=f;++i)
printf("%.7lf %.7lf\n",P[Q[i]].F,P[Q[i]].S);

return 0;
}