Cod sursa(job #1226776)

Utilizator thewildnathNathan Wildenberg thewildnath Data 7 septembrie 2014 14:43:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define NMAX 120010
#define INF 2000000000
#define EPS 0.0000001

struct punct
{
    double x,y,tan;
};
punct v[NMAX];

int n, num;
int st[NMAX];

inline bool egal0(const double &x)
{
    return x+EPS>=0 && x-EPS<=0;
}

inline int ccw(const punct &a, const punct &b, const punct &c)
{
    double x=(a.x-b.x)*(c.y-a.y)-(a.y-b.y)*(c.x-a.x);

    if(egal0(x))
        return 0;

    return x>0 ? 1 : -1;
}

inline bool cmpP(const punct &a, const punct &b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

inline bool cmpT(const punct &a, const punct &b)
{
    int x= ccw(v[0], a, b);

    if(x==0)
        return cmpP(a, b);

    return x < 0;
}


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

    int poz=0;

    scanf("%d", &n);
    for(int i=0; i<=n; ++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);

    sort(v, v+n, cmpP);
    sort(v+1, v+n, cmpT);
    v[n]=v[0];


    while(poz<=n)
    {
        if(ccw(v[st[num-1]], v[st[num]], v[poz]) >= 0 && num >= 1)
        {
            --num;
        }else
        {
            st[++num]=poz;
            ++poz;
        }
    }

    printf("%d\n", num);
    for(int i=0; i<num; ++i)
        printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);

    return 0;
}