Cod sursa(job #3246352)

Utilizator tudorhTudor Horobeanu tudorh Data 2 octombrie 2024 19:35:49
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
    long double x,y;
    bool type; ///1 = sus ,0 =jos
} punct[120001];
vector <Punct> s;
bool sortpuncte(Punct a,Punct b)
{
    return(a.x<b.x || (a.x==b.x && a.y<b.y));
}
bool sorttrig(Punct a,Punct b)
{
    return atan2(a.y,a.x)<atan2(b.y,b.x);
}
long double Arie(long double xa,long double ya,long double xb,long double yb,long double xc,long double yc)
{
    return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}
int main()
{
    int n;
    long double x,y;
    fin>>n;
    for(int i=0; i<n; i++)
    {
        fin>>x>>y;
        punct[i]= {x,y};
    }
    sort(punct,punct+n,sortpuncte);
    for(int i=1; i<n-1; i++)
    {
        long double arie=Arie(punct[0].x,punct[0].y,punct[n-1].x,punct[n-1].y,punct[i].x,punct[i].y);
        punct[i].type=arie>0;
    }
    punct[n-1].type=1;
    for(int i=0; i<n-1; i++)
    {
        if(punct[i].type)
            continue;
        while(s.size()>1)
        {
            long double arie=Arie(punct[i].x,punct[i].y,s[s.size()-2].x,s[s.size()-2].y,s[s.size()-1].x,s[s.size()-1].y);
            if(arie<0)
                s.pop_back();
            else break;
        }
        s.push_back(punct[i]);
    }
    int size0=s.size();
    punct[0].type=1;
    for(int i=n-1; i>=0; i--)
    {
        if(!punct[i].type)
            continue;
        while(s.size()-size0>1)
        {
            long double arie=Arie(punct[i].x,punct[i].y,s[s.size()-2].x,s[s.size()-2].y,s[s.size()-1].x,s[s.size()-1].y);
            if(arie<0)
                s.pop_back();
            else break;
        }
        s.push_back(punct[i]);
    }
    if(s[s.size()-1].x==punct[0].x && s[s.size()-1].y==punct[0].y)
        s.pop_back();
    fout<<s.size()<<'\n';
    sort(s.begin(),s.end(),sorttrig);
        for(int i=0;i<s.size();i++)
    fout<<(fixed)<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';
    return 0;
}