Cod sursa(job #3359393)

Utilizator malita.dragosMalita Dragos-Ionut malita.dragos Data 27 iunie 2026 17:57:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct Punct{
    double x,y;
};

Punct Prim;

double det(Punct A, Punct B, Punct C){
    return B.x*C.y + A.x*B.y + A.y*C.x - A.y*B.x - B.y*C.x - A.x*C.y;
}

double dist(Punct A,Punct B){
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

bool comp(Punct A,Punct B){
    double determinant = det(A,B,Prim);
    if(determinant != 0){
        return determinant>0;
    }
    return dist(Prim,A) < dist(Prim,B);
}

int main(){

    int n;
    fin>>n;
    vector<Punct> p(n);
    int prim=0;
    
    for(int i=0;i<n;i++){
        fin>>p[i].x>>p[i].y;
        if(p[i].y<p[prim].y || (p[i].y == p[prim].y && p[i].x >= p[prim].x)){
            prim=i;
        }
    }

    swap(p[0],p[prim]);
    Prim = p[0];

    sort(p.begin()+1,p.end(),comp);
    vector<Punct> inconjor;
    inconjor.push_back(p[0]);
    inconjor.push_back(p[1]);

    for(int i=2;i<n;i++){
        Punct penultim = inconjor[inconjor.size()-2], ultim = inconjor[inconjor.size()-1], curent=p[i];
        while(inconjor.size()>=2 && det(penultim,ultim,curent)<=0){
            inconjor.pop_back();
            if(inconjor.size()>=2)
                penultim = inconjor[inconjor.size()-2], ultim = inconjor[inconjor.size()-1], curent=p[i];
        }
        inconjor.push_back(curent);
    }

    fout<<inconjor.size()<< '\n';
    for(size_t i=0;i<inconjor.size();i++){
        fout<<fixed<<setprecision(6)<<inconjor[i].x<< " "<<inconjor[i].y<< '\n';
    }

    fin.close();
    fout.close();

    return 0;
}