Cod sursa(job #1242236)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 octombrie 2014 09:20:46
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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;
vector < int > Q;

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 (_i>=2 && P[i]<P[_i]) _i=i;
}

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

Q.push_back(1);
Q.push_back(2);

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

    Q.push_back(i);
}

printf("%d\n",Q.size());

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

return 0;
}