Cod sursa(job #2019707)

Utilizator IoanZioan zahiu IoanZ Data 8 septembrie 2017 12:58:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>


using namespace std;


const double eps=1.0e-14;

struct Point
{
    double x,y;
};

vector<Point>P;
vector<int>h;

Point LL;

double dist(Point P1,Point P2)
{
    return sqrt((P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.y));
}

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 c;
    c=cp(P1,P2,P3);
    if (fabs(c)<eps)
        return 0;
    if (c>=eps)
        return 1;
    return -1;
}

bool cmp(Point P1,Point P2)
{
    int c=ccw(LL,P1,P2);
    if (c==1)
        return 1;
    if (c==-1)
        return 0;
    double d1,d2;
    d1=dist(LL,P1);
    d2=dist(LL,P2);
    if (d1-d2<eps)
        return 1;
    return 0;
}

int main()
{
    int n,i,i2=-1,top;
    Point p,p1;
    p1.x=1000000001,p1.y=1000000001;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for (i=0; i<n; i++)
    {
        scanf("%lf%lf",&p.x,&p.y);
        if (p1.y-p.y>=eps)
        {
            p1.x=p.x;
            p1.y=p.y;
            i2=i;
        }
        else if (fabs(p1.y-p.y)<eps)
            if (p1.x-p.x>=eps)
            {
                p1.x=p.x;
                p1.y=p.y;
                i2=i;
            }
        P.push_back(p);
    }
    LL=P[i2];
    swap(P[0],P[i2]);
    sort(P.begin()+1,P.end(),cmp);
    P.push_back(P[0]);
    h.push_back(0);
    h.push_back(1);
    i=2;
    top=1;
    while (i<=n)
    {
        top=h.size()-1;
        if (ccw(P[h[top-1]],P[h.back()],P[i])>0)
        {
            h.push_back(i);
            i++;
        }
        else
            h.pop_back();
    }
    printf("%d\n",top+1);
    for (i=0;i<=top;i++)
        printf("%lf %lf\n",P[h[i]].x,P[h[i]].y);
        return 0;
}