Cod sursa(job #2332478)

Utilizator andreinichitaTirziu Nichita andreinichita Data 30 ianuarie 2019 19:39:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX=120005;
const double eps=1e-14;
struct POINT
{
    double x,y;
};
POINT v[NMAX],LL;
int h[NMAX];
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=cp(P1,P2,P3);
    if(fabs(c)<eps)
        return 0;
    if(c>=eps)
        return 1;
    return -1;
}
bool cmp(POINT P1,POINT P2)
{
    int sccw=ccw(LL,P1,P2);
    if(sccw>0)
        return 1;
    return 0;
}
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int main()
{
    int n,i,top;
    POINT temp;
    double X,Y;
    in>>n>>X>>Y;
    temp.x=X;
    temp.y=Y;
    v[0]=temp;
    for(i=1;i<n;i++)
    {
        in>>X>>Y;
        v[i].x=X;
        v[i].y=Y;
        if(((Y-v[0].y)<=-eps)||(fabs(Y-v[0].y)<eps&&(X-v[0].x)<=-eps))
            swap(v[0],v[i]);
    }
    LL=v[0];
    sort(v+1,v+n,cmp);
    v[n]=LL;
    h[1]=0;
    h[2]=1;
    top=2;
    i=2;
    while(i<=n)
    {
        if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    out<<top-1<<"\n";
    out<<fixed<<showpoint<<setprecision(6);
    for(i=1;i<top;i++)
        out<<v[h[i]].x<<" "<<v[h[i]].y<<"\n";
    return 0;
}