Cod sursa(job #2756504)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 1 iunie 2021 10:17:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin ("infasuratoare.in") ;
ofstream fout ("infasuratoare.out") ;
struct POINT
{
    double x, y ;
};
const int NMAX = 120000 ;
const double eps = 1.0e-14 ;
POINT P[NMAX + 5], LL ;
int h[NMAX + 5] ;
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)
{
    double crossp = cp(P1, P2, P3) ;
    if(fabs(crossp) < eps)
        return 0 ;
    if(crossp > -eps)
        return 1 ;
    return -1 ;
}
bool cmp (POINT &P1, POINT &P2)
{
    return ccw(LL, P1, P2) > 0 ;
}
double aria_poligon (int n)
{
    double aria ;
    int i ;
    P[n] = P[0] ;
    aria = 0 ;
    for(int i = 0 ; i <= n ; i++)
        aria = P[i].x * P[i + 1].y - P[i + 1].x * P[i].y ;
    aria = 0.5 * fabs(aria) ;
    return aria ;
}
int main()
{
    int n, i, top ;
    double a, b ;
    fin >> n >> a >> b ;
    P[0].x = a ;
    P[0].y = b ;
    for(i = 1 ; i < n ; i++)
    {
        fin >> a >> b ;
        P[i].x = a ;
        P[i].y = b ;
        if(P[i].y - P[0].y <= -eps or (fabs(P[i].y - P[0].y) < eps) and P[i].x - P[0].x <= -eps)
            swap(P[i], P[0]) ;
    }
    LL = P[0] ;
    P[n] = P[0] ;
    h[0] = 0 ;
    h[1] = 1 ;
    sort(P + 1, P + n, cmp) ;
    top = 1 ;
    i = 2 ;
    while(i <= n)
        if(ccw(P[h[top - 1]], P[h[top]], P[i]) > 0)
        {
            h[++top] = i ;
            i++;
        }
        else top--;
    fout << top << '\n' ;
    for(i = 0 ; i < top ; i++)
        fout << fixed << setprecision(6) << P[h[i]].x << ' ' << setprecision(6) << P[h[i]].y << '\n' ;
    return 0;
}