Cod sursa(job #1966082)

Utilizator Marcel.DragosMarcel Dragos Ignat Marcel.Dragos Data 14 aprilie 2017 21:14:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct {double x, y;}P[120001],st[120001],minim,aux;
int vf,n,i,poz;
double minx,miny,o;

bool cmp(punct A, punct B)
{
    if(atan(A.y/A.x)==atan(B.y/B.x))
        return sqrt((A.x-minim.x)*(A.x-minim.x) -(A.y-minim.y)*(A.y-minim.y))<sqrt((B.x-minim.x)*(B.x-minim.x)-(B.y-minim.y)*(B.y-minim.y));
        else
            return atan(A.y/A.x)<atan(B.y/B.x);
}

void pop()
{
    vf--;
}
void push(punct A)
{
    vf++;
    st[vf]=A;
}

double prod(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    minim.x=10000000;
    minim.y=10000000;
    for(i=1; i<=n; i++)
        {scanf("%lf%lf", &P[i].x, &P[i].y);
        if(P[i].x<minim.x)
            {minim=P[i];
            poz=i;}
            else
                if(P[i].x==minim.x)
                    if(P[i].y<minim.y)
                        {minim=P[i];
                        poz=i;}
            }
    aux=P[1];
    P[1]=P[poz];
    P[poz]=aux;
    sort(P+1,P+n+1,cmp);
    vf=0;
    push(P[1]);
    push(P[2]);
    for(i=3; i<=n; i++)
    {
        o=prod(st[vf-1],st[vf],P[i]);
        if(o==0)
        {
            pop();
            push(P[i]);
        }
        else
            if(o>0)
        {
            push(P[i]);
        }
            else
            {
                while(vf>1 && o<=0)
                {
                    pop();
                    o=prod(st[vf-1],st[vf],P[i]);
                }
                push(P[i]);
            }
    }

    printf("%d\n", vf+1);
    for(i=1; i<=vf; i++)
        printf("%lf %lf\n", st[i].x, st[i].y);
    printf("%lf %lf\n", minim.x, minim.y);
    return 0;
}