Cod sursa(job #1165162)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 aprilie 2014 15:25:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>

#define Nmax 120005
#define x first
#define y second

using namespace std;
int N,vf;
pair<double,double> pct[Nmax],S[Nmax];

double cross_product(pair<double,double> A,pair<double,double> B, pair<double,double> C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
class cmp{
public:
    bool operator()(const pair<double,double> &A,const pair<double,double> &B) const
    {
        double x = cross_product(pct[1],A,B);
        return (cross_product(pct[1],A,B) < 0);
    }
};

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

    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%lf%lf",&pct[i].x,&pct[i].y);
    int ind = 1;
    for(int i = 2; i <= N; ++i)
        if(pct[i] < pct[ind]) ind = i;
    swap(pct[1],pct[ind]);
    sort(pct+2,pct+N+1,cmp());
    S[++vf] = pct[1];S[++vf] = pct[2];
    for(int i = 3; i <= N; ++i)
    {
        while(vf >= 2 && cross_product(S[vf-1],S[vf],pct[i]) > 0)
            --vf;
        S[++vf] = pct[i];
    }
    printf("%d\n",vf);
    while(vf)
    {
        printf("%lf %lf\n",S[vf].x,S[vf].y);
        --vf;
    }
    return 0;
}