Cod sursa(job #3312537)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 28 septembrie 2025 23:29:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.79 kb
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ST1 l,(l+r)/2,node*2+1
#define ST2 (l+r)/2+1,r,node*2+2
#define STARGS ll l, ll r, ll node
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T, typename T2 = null_type>
    using ordered_set = tree<T, T2, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll getTime(){return chrono::steady_clock::now().time_since_epoch().count();}
mt19937_64 gen(getTime());
ll rndnext(ll l,ll r){
    uniform_int_distribution<ll> rng(l,r);
    return rng(gen);
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t Fixed_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + Fixed_RANDOM);
    }
};
const ll NMAX=2e5+5,MOD=998244353,STMAX=(1<<20)+5,LGMAX=18;
typedef long double ld;
struct vec2{
    ld x=0,y=0;
    vec2(){} vec2(ld a, ld b){x=a,y=b;}
}O2;
struct vec3{
    ld x=0,y=0,z=0;
    vec3(){} vec3(ld a, ld b, ld c){x=a,y=b;z=c;}
}O3;

const ld eps=1e-9;
vector<vec2> linecircleintersection(const vec3& l, const vec3& c){
    ld nc=l.z+l.x*c.x+l.y*c.y;
    ld h=(l.x*l.x+l.y*l.y);
    ld x0=-l.x*nc/h;
    ld y0=-l.y*nc/h;
    if(nc*nc>c.z*c.z*h+eps) return {};
    if(nc*nc>=c.z*c.z*h-eps) return {vec2(x0+c.x,y0+c.y)};
    ld d=sqrtl((c.z*c.z-nc*nc/h)/h);
    return {vec2(x0+d*l.y+c.x,y0-d*l.x+c.y),vec2(x0-d*l.y+c.x,y0+d*l.x+c.y)};
}
vector<vec2> circlecircleintersection(const vec3& a, const vec3& b){
    ld da=a.x-b.x, db=a.y-b.y;
    if(abs(da)<eps && abs(db)<eps)
        return vector<vec2>(abs(a.z-b.z)<eps?3:0);
    return linecircleintersection(vec3(2*da,2*db,
            (b.x*b.x+b.y*b.y-b.z*b.z)-
            (a.x*a.x+a.y*a.y-a.z*a.z)),a);
}
vec3 line(const vec2& a, const vec2& b){
    const ld A=b.y-a.y,B=a.x-b.x;
    return vec3(A,B,-(A*a.x+B*a.y));
}
int order(const vec2& a, const vec2& b, const vec2& c){
    ld area=(a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
    return area<0?-1:(area!=0);
}
vec3 line(const vec2& a, ld slope){
    return vec3(slope,-1,a.y-a.x*slope);
}
// computes the intersection between two lines a and b
bool intersect(const vec2& a, const vec2& b, const vec2& c, const vec2& d){
    if(order(a,b,c)==0 && order(a,b,d)==0){
        return max(min(a.x,b.x),min(c.x,d.x))<=min(max(a.x,b.x),max(c.x,d.x)) &&
               max(min(a.y,b.y),min(c.y,d.y))<=min(max(a.y,b.y),max(c.y,d.y));
    }
    return order(a,b,c)*order(a,b,d)<=0 && order(c,d,a)*order(c,d,b)<=0;
}
vec2 intersect(const vec3& a, const vec3& b){
 // assert(a.x*b.y-a.y*b.x);
    return vec2((a.y*b.z-a.z*b.y)/(a.x*b.y-a.y*b.x),
                (a.z*b.x-a.x*b.z)/(a.x*b.y-a.y*b.x));
}
// constructs plane from 3d points
struct vec4{
    ld x=0,y=0,z=0,w=0;
    vec4(){} vec4(ld a, ld b, ld c, ld d){x=a,y=b,z=c,w=d;}
}O4;
vec4 plane(const vec3& a, const vec3& b, const vec3& c) {
    vec3 n((b.y-a.y)*(c.z-a.z)-(b.z-a.z)*(c.y-a.y),
           (b.z-a.z)*(c.x-a.x)-(b.x-a.x)*(c.z-a.z),
           (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
    return vec4(n.x,n.y,n.z,-n.x*a.x-n.y*a.y-n.z*a.z);
}

vector<vec2> convex_hull(vector<vec2> v, int col=0){
    int n=v.size();
    if(n<3) return v;
    sort(v.begin(),v.end(),
    [](vec2 a, vec2 b){return a.x==b.x?a.y<b.y:a.x<b.x;});
    vec2 l=v[0],r=v.back();
    vector<vec2> u={l},d={l};
    for(int i=1;i<n;i++){
        vec2 it=v[i];
        if(i==n-1 || order(l,it,r)>=!col){
            while(u.size()>=2 && order(u[u.size()-2],u.back(),it)<!col) u.pop_back();
            u.push_back(it);
        }
        if(i==n-1 || order(l,it,r)<=col-1){
            while(d.size()>=2 && order(d[d.size()-2],d.back(),it)>col-1) d.pop_back();
            d.push_back(it);
        }
    }
    d.pop_back(); reverse(d.begin(),d.end());
    u.insert(u.end(),d.begin(),d.end()-1);
    return u;
}
void tc(){
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    ll n;
    fin>>n;
    vector<vec2> a;
    for(ll i=0;i<n;i++){
        ld x,y; fin>>x>>y; a.push_back(vec2(x,y));
    }
    a=convex_hull(a,0);
    fout<<a.size()<<'\n';
    reverse(a.begin(),a.end());
    fout<<fixed<<setprecision(9);
    for(auto it : a) fout<<it.x<<' '<<it.y<<'\n';
}
int main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //ll t; cin>>t; while(t--)
        tc();
    return 0;
}