Cod sursa(job #3215901)

Utilizator PetraPetra Hedesiu Petra Data 15 martie 2024 14:06:23
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

#define NMAX 120003

using namespace std;

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

struct point {
    double x, y;
};

point points[NMAX], leftPoint;
int n, leftPointIndex;
vector<point> v;

double det(point a, point b, point c)
{
    return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - a.x*c.y - c.x*b.y);
}

bool cmp(point a, point b)
{
    return det(leftPoint, a, b) >= 0;
}

void read_data()
{
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        double x, y;
        fin >> x >> y;
        points[i] = {x, y};

        if (x < points[leftPointIndex].x || (x == points[leftPointIndex].x && y < points[leftPointIndex].y))
            leftPointIndex = i;
    }
}

int main()
{
    read_data();

    swap(points[0], points[leftPointIndex]); // fixam pct initial pe 0
    leftPoint = points[0];

    sort(points + 1, points + n, cmp);

    v.push_back(leftPoint);
    for (int i = 1; i < n; i++)
    {
        while (v.size() > 1 && det(v[v.size()-2], v[v.size()-1], points[i]) < 0)
            v.pop_back();

        v.push_back(points[i]);
    }

    fout << v.size() << "\n";
    for (int i = 0; i < v.size(); i++)
        fout << fixed << v[i].x << " " << v[i].y << "\n";

    return 0;
}