Cod sursa(job #3213319)

Utilizator radu._.21Radu Pelea radu._.21 Data 12 martie 2024 21:30:47
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct pct{
    double x; double y;
}v[200001],st[200001];
pct ori;
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool cmp(pct i, pct j) {
    /*if(i.x==ori.x && i.y == ori.y)
        return 0;
    if(j.x==ori.x && j.y == ori.y)
        return 1; */
    return (i.x - ori.x) * (j.y - ori.y) > (j.x - ori.x) * (i.y - ori.y);
}
double semn(double xi1, double yi1,double xi2,double yi2, double xi3,double yi3) {
    return xi1 * yi2 + xi2 * yi3 + xi3 * yi1 - yi1 * xi2 - yi2 * xi3 - yi3 * xi1;
}
int main(){
    fin>>n;
    ori.y = 1000000000;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[i].y<ori.y)
            ori=v[i];
        else if(v[i].y==ori.y && v[i].x<ori.x)
             ori=v[i];
    }
    for(int i=1;i<=n;i++)
        v[i].x-=ori.x,v[i].y-=ori.y;
    sort(v+1,v+n+1,cmp);
    st[1]=v[1];
    st[2]=v[2];
    int k = 2;

    for(int i = 3;i<=n;i++){
        while(semn(st[k-1].x,st[k-1].y,st[k].x,st[k].y,v[i].x,v[i].y)<0){
            k--;
        }
        st[++k]=v[i];
    }
    fout<<k<<'\n';
    fout<<fixed<<setprecision(15);
    fout<<st[k].x<<" "<<st[k].y<<'\n';
    for(int i=1;i<k;i++)
        fout<<st[i].x+ori.x<<" "<<st[i].y+ori.y<<'\n';
    return 0;
}