Cod sursa(job #2989271)

Utilizator Luka77Anastase Luca George Luka77 Data 6 martie 2023 12:03:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point
{
    double x, y;  
};
const int NMAX = 120005;
int n;
int idx[NMAX];
point points[NMAX];

inline 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 - c.x*b.y - a.x*c.y);
}

inline bool Trig(const point &a, const point &b)
{
    return det(points[1], a, b) > 0;
}

inline void solution()
{
    int minY = points[1].y, minpoz = 1;
    for(int i = 1; i <= n; ++ i)
    {
        if(minY > points[i].y)
        {
            minY = points[i].y;
            minpoz = i;
        }
    }
    
    swap(points[1], points[minpoz]);
    
    sort(points + 2, points + n + 1, Trig);
    
    int k = 2;
    idx[1] = 1;
    idx[2] = 2;
    
    for(int i = 3; i <= n; ++ i)
    {
        while(k > 1 && det(points[idx[k-1]], points[idx[k]], points[i]) <= 0) 
            k--;
        idx[++k] = i;
    }
    
    fout << k << '\n';
    
    for(int i = 1; i <= k; ++ i)
        fout << fixed << setprecision(12) << points[idx[i]].x << ' ' << points[idx[i]].y << '\n';
}

int main()
{
    fin >> n;
    
    for(int i = 1; i <= n; ++ i)
        fin >> points[i].x >> points[i].y;
        
    solution();
}