Cod sursa(job #1341278)

Utilizator stefantrettTrett Stefan stefantrett Data 12 februarie 2015 16:39:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <algorithm>
#include <iostream>

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

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

double det(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
    {
        return (det(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 && det(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;
}