Cod sursa(job #2402467)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 10 aprilie 2019 18:45:41
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 2.e9;
const double PI = 2.0 * acos(0.0);
const double eps = 1.e-12;
struct POINT
{
    double x, y, a;
};
POINT P[120005];
double cmp(POINT a, POINT b)
{
    return a.a < b.a;
}
double cp(POINT P1, POINT P2, POINT P3)
{
    return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
    double ccp;
    ccp = cp(P1, P2, P3);
    if(fabs(ccp) < eps)
        return 0;
    if(ccp > eps)
        return 1;
    return -1;
}
int st[120005];
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, i, ind, top;
    double tx, ty, miny, minx;
    scanf("%d", &n);
    miny = INF;
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%lf%lf", &tx, &ty);
        P[i].x = tx;
        P[i].y = ty;
        if(ty < miny)
        {
            miny = ty;
            minx = tx;
            ind = i;
        }
        else if(ty == miny && tx < minx)
        {
            minx = tx;
            ind = i;
        }
    }
    for(i = 1 ; i <= n ; i ++)
        if(i != ind)
            P[i].a = atan2(P[i].y - miny, P[i].x - minx);
    P[ind].a = -1;
    sort(P + 1, P + n + 1, cmp);
    P[n + 1] = P[1];
    top = 2;
    st[1] = 1;
    st[2] = 2;
    for(i = 3 ; i <= n + 1 ; i ++)
    {
        while(top >= 2 && ccw(P[st[top - 1]], P[st[top]], P[i]) == -1)
            top --;
        st[++ top] = i;
    }
    printf("%d\n", top - 1);
    for(i = 1 ; i < top ; i ++)
        printf("%f %f\n", P[st[i]].x, P[st[i]].y);
    return 0;
}