Cod sursa(job #3276588)

Utilizator WiseAndrei4Vetrila Andrei WiseAndrei4 Data 13 februarie 2025 21:25:36
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream gout("infasuratoare.out");
struct pct
{
    double x,y;
};
int orientation(const pct&a,const pct&b,const pct&c)
{
    double val=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if(!val)return 0;
    if(val>0)return 1;
    else return 2;
}
double dist(const pct&p1,const pct&p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
bool compare(const pct &p0, const pct &p1, const pct &p2)
{
    int o=orientation(p0,p1,p2);
    if(o==0)return dist(p0,p1)<dist(p0,p2);
    return o==2;
}
int main()
{
    int n;
    fin>>n;
    vector<pct>v(n);
    for(int i=0; i<n; ++i)fin>>v[i].x>>v[i].y;
    v.erase(unique(v.begin(), v.end(), [](const pct &a, const pct &b)
    {
        return a.x == b.x && a.y == b.y;
    }), v.end());
    pct p0=*min_element(v.begin(),v.end(),[](const pct &a, const pct &b)
    {
        return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
    });
    sort(v.begin(),v.end(),[&p0](const pct &p1,const pct &p2)
    {
        return compare(p0,p1,p2);
    });
    vector<pct>ans;
    ans.push_back(v[0]);
    ans.push_back(v[1]);
    ans.push_back(v[2]);
    for(int i=3; i<v.size(); ++i)
    {
        while(ans.size()>1&&
                orientation(ans[ans.size()-2],ans.back(),v[i])!=2)ans.pop_back();
        ans.push_back(v[i]);
    }
    p0=ans.front();
    sort(ans.begin(),ans.end(),[&p0](const pct&a,const pct&b)->bool
    {
        return atan2(a.y-p0.y,a.x-p0.x)<atan2(b.y-p0.y,b.x-p0.x);
    });
    gout<<ans.size()<<'\n';
    while(!ans.empty())
    {
        gout<<fixed<<setprecision(12)<<ans.back().x<<' '<<ans.back().y<<'\n';
        ans.pop_back();
    }
    return 0;
}