Cod sursa(job #1393610)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 19 martie 2015 16:59:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
// How about a coding trick?
#include <cstdio>
#include <algorithm>
#define DIM 120120
using namespace std;
FILE *fin=freopen("infasuratoare.in","r",stdin);
FILE *fout=freopen("infasuratoare.out","w",stdout);

struct Point{
                double x, y;
            };
Point P[DIM], Stack[DIM];
int cnt;
int n;

double produs(Point P1, Point P2, Point P3)
{
    return ( P2.x - P1.x ) * ( P3.y - P1.y ) - ( P3.x - P1.x ) * ( P2.y - P1.y );
}


void Read()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf%lf", &P[i].x, &P[i].y);
}

void Find_Min()
{
    int k = 1;
    for(int i = 2; i <= n; ++i)
        if( P[i].y < P[k].y || (P[i].y == P[k].y && P[i].x < P[k].x) )
            k = i;
    swap(P[1], P[k]);
}

inline bool comp(Point a, Point b)
{
    return  produs(P[1], a, b) > 0 ;
}

void Solve()
{
    Find_Min();
    sort(P + 2, P + n + 1, comp);
    Stack[1] = P[1], Stack[2] = P[2], cnt = 2;

    double val;
    for(int i = 3; i <= n; ++i)
    {
        val = produs(Stack[cnt - 1], Stack[cnt], P[i]);
        if( val == 0 )
            Stack[cnt] = P[i];
        else
        {
            if( val < 0 )
                while( val <= 0 && cnt >= 2 )
                {
                    --cnt;
                    val = produs(Stack[cnt - 1], Stack[cnt], P[i]);
                }
            ++cnt, Stack[cnt] = P[i];
        }
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; ++i)
        printf("%.6f %.6f\n", Stack[i].x, Stack[i].y);
}

int main()
{
    Read();
    Solve();
    return 0;
}