Cod sursa(job #1168155)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 7 aprilie 2014 09:43:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int NMAX = 120000+5;

struct Point
{
    double x,y;
    Point()
    {
        x = y = 0;
    }
};

double Cross_Product(const Point &A,const Point &B,const Point &C)
{
    return (A.x - C.x) * (B.y - C.y) - (B.x - C.x) * (A.y - C.y);
}

void Read(),Solve(),Print();

int N;
Point P[NMAX];
int S[NMAX],top;

struct cmp
{
    bool operator()(const Point &A, const Point &B)
    {
        return Cross_Product(P[1],A,B) > 0;
    }
};

void Get_Leftmost_Downmost_Point()
{
    int i,j = 1;
    for(i = 2; i <= N; i++)
        if(P[i].x == P[j].x && P[i].y < P[j].y) j = i;
        else if(P[i].x < P[j].x) j = i;
    swap(P[1],P[j]);
}

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    int i;

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

    scanf("%d",&N);

    for(i = 1; i <= N; i++)
        scanf("%lf%lf",&P[i].x,&P[i].y);
}

void Solve()
{
    int i;

    Get_Leftmost_Downmost_Point();

    sort(P+2,P+N+1,cmp());

    for(i = 1; i <= N; i++)
    {
        while(top >= 2 && Cross_Product(P[S[top-1]],P[S[top]],P[i]) < 0) top--;
        S[++top] = i;
    }
}

void Print()
{
    int i;

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

    for(i = 1; i <= top; i++)
        printf("%lf %lf\n",P[S[i]].x,P[S[i]].y);
}