Cod sursa(job #2756512)

Utilizator TudorNicorescuNicorescu Tudor TudorNicorescu Data 1 iunie 2021 10:44:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const double eps=1.0e-14;
const double INF=1e9;
const int NMAX = 120000;
struct Point
{
    double x,y;
};

Point P[NMAX+5], LL;
int h[NMAX+5];

double cp(const Point &P1,const Point &P2,const Point &P3)///aria paralelogramului
{
    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)///sensul vectorial
{
    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 arie_poligon(int n)
{
    double aria;
    int i;
    P[n] = P[0];
    aria = 0;
    for(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;
    out << fixed;
    in >> n >> a >> b;
    P[0].x = a;
    P[0].y = b;
    for(int i = 1; i< n; ++i)
    {
        in >> a >> b;
        P[i].x = a;
        P[i].y = b;
        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[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;
        }
    }
    out << top << "\n";
    for(i = 0; i < top; i++)
    {
        out << setprecision(6) << P[h[i]].x << " " <<  setprecision(6) << P[h[i]].y << "\n";
    }
    return 0;
}