Cod sursa(job #3212538)

Utilizator paull122Paul Ion paull122 Data 11 martie 2024 21:13:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

#define NMAX 120000
#define ll unsigned long long
#define MOD 1000000007
using namespace std;

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


struct pt
{
    double x,y;
} points[NMAX+1];
int n;

double det(pt a,pt b,pt c)
{
    return (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y);
}
bool cmp(pt a,pt b)
{
    return det(points[1],a,b) < 0;
}
vector<pt> S;
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> points[i].x >> points[i].y;
    }
    int start=1;
    for(int i=2;i<=n;i++)
    {
        if(points[i].y < points[start].y || (points[i].y==points[start].y && points[i].x < points[start].x))
        {
            start=i;
        }
    }
    swap(points[start],points[1]);

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

    for(int i=1;i<=2;i++)
    {
        S.push_back(points[i]);
    }
    for(int i=3;i<=n;i++)
    {
        while(S.size() >= 2 && det(S[S.size()-2],S[S.size()-1],points[i]) >= 0)
        {
            S.pop_back();
        }
        S.push_back(points[i]);
    }
    fout << S.size() << "\n";
    for(auto i : S)
    {
        fout << setprecision(6) << fixed << i.x << " " << i.y << "\n";
    }

}