Cod sursa(job #3222270)

Utilizator Uriesu_IuliusUriesu Iulius Uriesu_Iulius Data 9 aprilie 2024 16:55:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point
{
    double x, y;
};

const int mxN = 120001;
int n, k;
point pts[mxN], ans[mxN];

void readInput()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> pts[i].x >> pts[i].y;
    }
}

double orientation(point A, point B, point C)
{
    /*
    two lines: AB and BC
    mAB = (yB - yA) / (xB - xA)
    mBC = (yC - yB) / (xC - xB)

    mAB == mBC => collinear 0
    mBC > mAB => counterclockwise (ccw) +
    mBC < mAB => clockwise (cw) -
    */

    return (C.y - B.y) * (B.x - A.x) - (C.x - B.x) * (B.y - A.y);
}

bool compare(point A, point B)
{
    // should return true if 'A < B'
    if (orientation(pts[1], A, B) > 0) // ccw
    {
        return true;
    }
    return false;
}

void ccwSort()
{
    int idx = 1;
    for (int i = 2; i <= n; i++)
    {
        if (pts[i].y < pts[idx].y || pts[i].y == pts[idx].y && pts[i].x < pts[idx].x)
        {
            idx = i;
        }
    }
    swap(pts[1], pts[idx]);
    sort(pts + 2, pts + n + 1, compare);

    /*
    for (int i = 2; i <= n; i++)
    {
        double m = (pts[i].y - pts[1].y) / (pts[i].x - pts[1].x);
        cout << m << "\n";
    }
    */
}

void convexHull()
{
    ans[++k] = pts[1];
    ans[++k] = pts[2];

    for (int i = 3; i <= n; i++)
    {
        while (k >= 2 && orientation(ans[k - 1], ans[k], pts[i]) < 0)
        { // as long as they are cw, the last one is problematic
            k--;
        }
        ans[++k] = pts[i];
    }
}

void displayAnswer()
{
    fout << k << "\n";
    for (int i = 1; i <= k; i++)
    {
        fout << setprecision(20) << ans[i].x << " " << ans[i].y << "\n";
    }
}

int main()
{
    readInput();
    ccwSort();
    convexHull();
    displayAnswer();

    return 0;
}