Cod sursa(job #2176197)

Utilizator DragosArseneDragos Arsene DragosArsene Data 16 martie 2018 21:29:13
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
double minx, miny, maxx, maxy;
struct ic{double x, y;};
struct stiva{int poz, afis;};
double arie(double qx, double qy){
return (minx*maxy+maxx*qy+qx*miny-qx*maxy-maxx*miny-minx*qy)/2;

}
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;
    int n, i, k, j, cant;
    stiva st[120000];
    ic v[120000];
    vector <double> stgx, stgy, drx, dry;

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);
minx=v[1].x;
miny=v[1].y;
maxx=v[n].x;
maxy=v[n].y;
for(i=1;i<=n;i++){
    if(arie(v[i].x, v[i].y)<=0){
        drx.push_back(v[i].x);
        dry.push_back(v[i].y);
    }
    if(arie(v[i].x, v[i].y)>=0){
        stgx.push_back(v[i].x);
        stgy.push_back(v[i].y);
    }

}

k=0;
st[0].poz=0;
for(i=1;i<drx.size();i++){
        cant=drx.size();
        miny=dry[st[k].poz];
        minx=drx[st[k].poz];

        maxx=drx[i+1];
        maxy=dry[i+1];

    if(arie(drx[i], dry[i]) < 0){
        st[++k].poz=i;
        st[k].afis=1;
    }
}

for(i=stgx.size()-2;i>=1;i--){
        maxy=stgy[st[k].poz];
        maxx=stgx[st[k].poz];
        minx=stgx[i-1];
        miny=stgy[i-1];

    if(arie(stgx[i], stgy[i]) > 0){
        st[++k].poz=i;
        st[k].afis=0;
}
}
fprintf(fout,"%d\n", k+1);
for(j=0;j<=k;j++){
    if(st[j].afis==1)
        fprintf(fout,"%f %f\n", drx[st[j].poz],dry[st[j].poz]);
    else
        fprintf(fout,"%f %f\n", stgx[st[j].poz],stgy[st[j].poz]);
}
fclose(fin);
fclose(fout);
    return 0;
}