Cod sursa(job #2753935)

Utilizator teodormilitaruMilitaru Teodor teodormilitaru Data 24 mai 2021 19:09:12
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iostream>
const double eps = 1.0e-14;
const int NMAX = 120000;

struct POINT
{
    double x, y;
};

double cp (const POINT& p1, const POINT& p2, const POINT& p3)
{
    return ((p2.x - p1.x) * (p3.y-p2.y) - (p2.y-p1.y) * (p3.x-p2.x));
}

int ccw (const POINT& p1, const POINT& p2, const POINT& p3)
{
    /// 1 ccw 0 coliniar -1 cw
    double c = cp (p1, p2, p3);
    if (fabs(c) < eps)
        return 0;
    if (c >= eps)
        return 1;
    return -1;
}

POINT P[NMAX+5];
POINT LL;
int h[NMAX+5];

bool cmp (POINT p1, POINT p2)
{
    return (ccw(LL, p1, p2) > 0);
}

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int main ()
{
    int n,i,top;
    fin>>n;
    fin>>P[0].x>>P[0].y;
    for(i=1;i<n;i++)
    {
        fin>>P[i].x>>P[i].y;
        if(P[i].y - P[0].y<=-eps || (fabs(P[i].y-P[0].y)<eps && P[i].x - P[0].x<=-eps))
            swap (P[0],P[i]);
    }
    LL=P[0];
    sort (P+1,P+n, cmp);
    h[0]=0;
    h[1]=1;
    top=1;
    P[n]=P[0];
    i=2;
    while(i<=n)
    {
        if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    //for(i=0;i<top;i++)
      //  fout<<h[i]<<" ";
    //fout<<"\n";
    fout<<top<<"\n";
    for(i=0;i<top;i++)
    {
        fout<<P[h[i]].x<<" "<<P[h[i]].y<<"\n";
    }
}