Cod sursa(job #2173216)

Utilizator DragosArseneDragos Arsene DragosArsene Data 15 martie 2018 21:09:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
double minx, miny, maxx, maxy;
struct ic{double x, y;};
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, stg, j;
    int st[100000];
    ic v[10000];
    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;
drx.push_back(v[1].x);
dry.push_back(v[1].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=1;
st[0]=0;
st[1]=1;
for(i=2;i<drx.size();i++){
    st[++k]=i;
    if(dry[st[k-1]]<dry[st[k]]){
        miny=dry[st[k-1]];
        minx=drx[st[k-1]];
        maxx=drx[st[k]];
        maxy=dry[st[k]];
    }
    else{
    maxy=dry[st[k-1]];
    maxx=drx[st[k-1]];
    minx=drx[st[k]];
    miny=dry[st[k]];
    }
    if(arie(drx[i], dry[i])>= 0)
        k--;
}

for(i=stgx.size()-1;i>=0;i--){
    if(stgy[st[k-1]]<stgy[st[k]]){
        miny=stgy[st[k-1]];
        minx=stgx[st[k-1]];
        maxx=stgx[st[k]];
        maxy=stgy[st[k]];
    }
    else{
    maxy=dry[st[k-1]];
    maxx=drx[st[k-1]];
    minx=drx[st[k]];
    miny=dry[st[k]];
    }
    if(arie(v[i].x, v[i].y)<= 0)
        st[k]=i;
    else
        st[++k]=i;
}
for(j=0;j<=k;j++){
    fprintf(fout,"%lf %lf\n", v[st[k]].x, v[st[k]].y);
}
fclose(fin);
fclose(fout);
    return 0;
}