Cod sursa(job #2196191)

Utilizator DragosArseneDragos Arsene DragosArsene Data 18 aprilie 2018 18:39:05
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <iostream>
#include<stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct ic{double x, y;};
ic rez [120001];
int minx, miny, maxx, maxy;
double arie(double qx, double qy){
return (minx - qx) * (maxy - qy) - (miny - qy) * (maxx - qx);

}
bool cmp(ic a, ic b){
if(a.y < b.y)
    return true;
else{
    if(a.y==b.y){
        if(a.x<b.x)
        return true;
        else
        return false;
    }
    else
    return false;


}
}
int main() {
    FILE *fin, *fout;
    ic v[120001];
    int i, j, ii, jj, n, h, lg, cont;
    vector <double> drx, dry, stgx, stgy;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
fscanf(fin,"%d", &n);
for(i=1;i<=n;i++){
    fscanf(fin,"%lf%lf", &v[i].x, &v[i].y);
}

sort(v+1,v+n+1,cmp);

drx.push_back(v[1].x);
dry.push_back(v[1].y);
for(i=2;i<=n;i++){
        h=drx.size()-1;
        minx=v[1].x;
        miny=v[1].y;
        maxx=v[n].x;
        maxy=v[n].y;
        if(arie(v[i].x, v[i].y) <= 0){
        if(h>=1){

        minx=drx[h-1];
        miny=dry[h-1];
        maxx=drx[h];
        maxy=dry[h];
        while(arie(v[i].x, v[i].y) <= 0&&h>=1){
            drx.pop_back();
            dry.pop_back();
            h--;
        minx=drx[h-1];
        miny=dry[h-1];
        maxx=drx[h];
        maxy=dry[h];
        }
        }
        drx.push_back(v[i].x);
        dry.push_back(v[i].y);
        }
}

stgx.push_back(v[n].x);
stgy.push_back(v[n].y);
for(i=n-1;i>=1;i--){
    h=stgx.size()-1;
    minx=v[n].x;
    miny=v[n].y;
    maxx=v[1].x;
    maxy=v[1].y;
    if(arie(v[i].x, v[i].y) <= 0){
        if(h>=1){

        minx=stgx[h-1];
        miny=stgy[h-1];
        maxx=stgx[h];
        maxy=stgy[h];
        while(arie(v[i].x, v[i].y) <= 0&&h>=1){
            stgx.pop_back();
            stgy.pop_back();
            h--;
        minx=stgx[h-1];
        miny=stgy[h-1];
        maxx=stgx[h];
        maxy=stgy[h];
        }
        }
        stgx.push_back(v[i].x);
        stgy.push_back(v[i].y);
    }

}


drx.pop_back();
stgx.pop_back();
dry.pop_back();
stgy.pop_back();
ii=0;
jj=0;
cont=0;
fprintf(fout,"%d\n", drx.size()+stgx.size());
for(i=0;i<=drx.size()-1;i++){
    fprintf(fout,"%lf %lf\n", drx[i], dry[i]);
}
for(i=0;i<=stgx.size()-1;i++){
    fprintf(fout,"%lf %lf\n", stgx[i], stgy[i]);
}



fclose(fin);
fclose(fout);

    return 0;
}