Cod sursa(job #2753937)

Utilizator ASebastianA Sebastian ASebastian Data 24 mai 2021 19:12:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

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 cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int main()
{
    int n, i, top;
    cin >> n;
    cin >> P[0].x >> P[0].y;
    for (i=1; i<n; i++)
    {
        cin >> P[i].x >> P[i].y;
        if (P[i].y - P[0].y <= -eps || fabs(P[i].y - P[0].y) < eps and 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++)
//        cout << h[i] << " ";
//
//    cout << "\n";

    cout << top << "\n";
    for (i=0; i<top; i++)
        cout << fixed << setprecision(6) << P[h[i]].x << " " << P[h[i]].y << "\n";
    return 0;
}