Cod sursa(job #3292478)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 8 aprilie 2025 13:04:30
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <bits/stdc++.h>
#define VMAX 120005
#define INF 2000000000
#define int long long int
#define double long double
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct pct{
double x;
double y;
};
pct puncte[VMAX];
vector<int> infasuratoare;

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


bool comp(pct a, pct b)
{
    return arie_semn(puncte[1],a,b)>0;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    pct mini;
    mini.x=INF;
    mini.y=INF;

    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>puncte[i].x>>puncte[i].y;
        if(mini.x>puncte[i].x || mini.x==puncte[i].x && mini.y>puncte[i].y)
        {
            mini=puncte[i];
            nr=i;
        }
    }
    swap(puncte[1],puncte[nr]);

    sort(puncte+2, puncte+n+1, comp);
    infasuratoare.push_back(1);
    infasuratoare.push_back(2);
    for(i=3;i<=n;i++)
    {
        while(infasuratoare.size()>2 && ( arie_semn(puncte[i],puncte[infasuratoare[infasuratoare.size()-1]],puncte[infasuratoare[infasuratoare.size()-2]])>0 ) )
            infasuratoare.pop_back();
        infasuratoare.push_back(i);
    }
    // ultimul va intra garantat?
    fout<<infasuratoare.size()<<'\n';
    for(i=0;i<infasuratoare.size();i++)
        fout<<puncte[infasuratoare[i]].x<<' '<<puncte[infasuratoare[i]].y<<'\n';



    return 0;
}