Cod sursa(job #2551544)

Utilizator anamaria_panait.10Panait Ana-Maria anamaria_panait.10 Data 19 februarie 2020 22:03:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.82 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
using namespace std;

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

struct punct{
    float x, y;
}p[120001];

int nrPctInfasConv = 0;
punct raspuns[120001];
int ind = 0;

punct SemiplanulStang[100001], SemiplanulDrept[100001];
int ind1 = 0, ind2 = 0;
punct pctStanga, pctDreapta;

void calculSemiplan(punct p){
    //calculam determinantul triunghiului format de dr formata de pctStranga si pctDreapta si punctul dat ca param
    //si dupa putem decide in ce semiplan se afla punctul fata de dreapta form din pctStanga si pctDreapta
    double det = pctStanga.x*pctDreapta.y + pctDreapta.x*p.y + pctStanga.y*p.x - p.x*pctDreapta.y - pctStanga.x*p.y - pctDreapta.x*pctStanga.y;
    if(det < 0){ //atunci apartine semiplnului drapta sau jos
        SemiplanulDrept[++ind1] = p;
    }
    if(det > 0){ //atunci apartine semiplnului stanga sau sus
        SemiplanulStang[++ind2] = p;
    }
}

int comp1(punct a, punct b){
    if(a.x < b.x){
        return 1;
    }
    else if(a.x == b.x && a.y < b.y){
        return 1;
    }
    return 0;
}

punct st[100001];
int k;

void InfasuratoareStanga(){
    st[0] = pctStanga;
    st[1] = SemiplanulStang[1];
    k = 1;
    for(int i = 2; i <= ind2; i++){
        punct p = SemiplanulStang[i];
        double det = st[k].x*st[k-1].y + st[k-1].x*p.y + st[k].y*p.x - p.x*st[k-1].y - st[k].x*p.y - st[k-1].x*st[k].y;
        if(det > 0){ //dc pct se afla in dr sau jos
            k++;
            st[k] = p;
        }else{
            st[k] = p;
        }
    }
}
void InfasuratoareDreapta(){
    st[1] = pctStanga;
    st[2] = SemiplanulDrept[1];
    k = 2;
    for(int i = 2; i <= ind1; i++){
        punct p = SemiplanulDrept[i];
        double det = st[k].x*st[k-1].y + st[k-1].x*p.y + st[k].y*p.x - p.x*st[k-1].y - st[k].x*p.y - st[k-1].x*st[k].y;
        if(det < 0){ //dc pct se afla in dr sau jos
            k++;
            st[k] = p;
        }else{
            st[k] = p;
        }
    }
    st[++k] = pctDreapta;
}


int main() {
    int n;
    in >> n;
    int a, b;

    //initializam pct stg si dr
    pctStanga.x = 1000000001;
    pctDreapta.x = -1000000001;

    for(int i = 1; i <= n; i++){
        in >> p[i].x >> p[i].y;
        if(p[i].x < pctStanga.x){
            pctStanga = p[i];
        }
        else if(p[i].x == pctStanga.x && p[i].y < pctStanga.y){
            pctStanga = p[i];
        }

        if(p[i].x > pctDreapta.x){
            pctDreapta = p[i];
        }
        else if(p[i].x == pctDreapta.x && p[i].y > pctDreapta.y){
            pctDreapta = p[i];
        }
    }

    //grupam punctele pe semiplane
    for(int i = 1; i <= n; i++){
        if((p[i].x != pctStanga.x || p[i].y != pctStanga.y) && (p[i].x != pctDreapta.x || p[i].y != pctDreapta.y)){ //dc pct curent nu e nici pct cel mai din stanga si nici pct cel mai din dreapta
            calculSemiplan(p[i]);
        }
    }

    //sortam dupa x
    sort(SemiplanulDrept + 1, SemiplanulDrept + ind1, comp1);
    sort(SemiplanulStang + 1, SemiplanulStang + ind2, comp1);

//    for(int i = 1; i <= ind1; i++){
//        out << SemiplanulDrept[i].x <<" "<< SemiplanulDrept[i].y <<'\n';
//    }
//
//    out <<'\n';
//    for(int i = 1; i <= ind2; i++){
//        out << SemiplanulStang[i].x <<" "<< SemiplanulStang[i].y <<'\n';
//    }
    InfasuratoareStanga();
    nrPctInfasConv += k;
    for(int i = k; i >= 1; i--){
        raspuns[++ind] = st[i];
    }

    InfasuratoareDreapta();
    nrPctInfasConv += k;
    for(int i = 1; i <= k; i++){
        raspuns[++ind] = st[i];
    }
    out << nrPctInfasConv<<'\n';
    out <<setprecision(6) << fixed;
    for(int i = 1; i <= ind; i++){
        out << raspuns[i].x <<' '<< raspuns[i].y <<'\n';
    }

}