Cod sursa(job #3268825)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 17 ianuarie 2025 18:24:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#define pdd pair<double,double>
#define x first
#define y second
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const int NMAX = 120001;
pdd refPoint;
pdd operator- (pdd p1, pdd p2)
{
    return make_pair (p1.x - p2.x, p1.y - p2.y);
}
ostream& operator<< (ostream& os, pdd p1)
{
    os << p1.x << ' ' << p1.y << '\n';
    return os;
}
int main()
{
    int N;
    f >> N;
    vector<pdd> points (N + 1);
    double maxCoordX = - 2e9;
    int indMaxP = 0;
    for (int i = 1; i <= N; i++)
    {
        f >> points[i].x >> points[i].y;
        if (points[i].x > maxCoordX)
        {
            maxCoordX = points[i].x;
            indMaxP = i;
        }
        else if (points[i].x == maxCoordX)
        {
            if (points[i].y < points[indMaxP].y)
            {
                indMaxP = i;
            }
        }
    }
    refPoint = points[indMaxP];
    function<double (pdd, pdd) > dist = [] (pdd p1, pdd p2) -> double
    {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    };
    ///returns the area of the parallelogram p1p2 + p1p3
    auto computeAngle = [] (pdd p1, pdd p2, pdd p3) -> double
    {
        pdd p2t = p2 - p1;
        pdd p3t = p3 - p1;
        return (p2t.x * p3t.y - p3t.x * p2t.y);
    };
    sort (points.begin() + 1, points.end(), [&] (pdd p1, pdd p2) -> bool
    {
        double angle = computeAngle (refPoint, p1, p2);
        return angle == 0 ? dist (p1, refPoint) < dist (p2, refPoint) : angle < 0;
    });
    vector<pdd> convexHull;
    convexHull.pb (refPoint);
    for (int i = 2; i <= N; i++)
    {
        while (convexHull.size() > 1 &&
                computeAngle (convexHull.back(), * (convexHull.rbegin() + 1), points[i]) < 0)
        {
            convexHull.pop_back();
        }
        convexHull.pb (points[i]);
    }
    g << convexHull.size() << '\n';
    refPoint = mp (0, 0);
    sort (convexHull.begin(), convexHull.end(), [&] (pdd p1, pdd p2) -> bool
    {
        double angle = computeAngle (refPoint, p1, p2);
        return angle == 0 ? dist (p1, refPoint) < dist (p2, refPoint) : angle > 0;
    });
    for (const auto &p : convexHull)
    {
        g << fixed << setprecision (12) << p;
    }
    return 0;
}