Cod sursa(job #2542455)

Utilizator yo_andrei_2003Murica Andrei yo_andrei_2003 Data 9 februarie 2020 23:48:27
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <cstdio>
#include <algorithm>

using namespace std;
struct coord {
    double x, y;
};
int i, l, n;
coord v[120002], sts[120002], stt[12002];
void drp(double x, double y) {
    double a, b;
    int st=1;
    if (x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y<0) {
        while (i>1 && st==1) {
        a=x*(-stt[i-1].y+stt[i-2].y)-y*(stt[i-2].x-stt[i-1].x)+stt[i-2].x*stt[i-1].y-stt[i-1].x*stt[i-2].y;
        st=0;
        if (a>0) {
            i--;
            st=1;
        }
        }
        stt[i].y=y;
        stt[i].x=x;
        i++;
    }
    if (x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y>0) {
        while (l>1 && st==1) {
        a=x*(-sts[l-1].y+sts[l-2].y)-y*(sts[l-2].x-sts[l-1].x)+sts[l-2].x*sts[l-1].y-sts[l-1].x*sts[l-2].y;
        st=0;
        if (a<0) {
            l--;
            st=1;
        }
        }
        sts[l].y=y;
        sts[l].x=x;
        l++;
    }
    b=x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y;
    a=x*(-stt[i-1].y+stt[i-2].y)-y*(stt[i-2].x-stt[i-1].x)+stt[i-2].x*stt[i-1].y-stt[i-1].x*stt[i-2].y;
    printf("%lf %lf\n" ,b ,a);
}
bool cmp (coord a, coord b){
    return a.y<b.y;
}
int main()
{
    int k;
    FILE *fin, *fout;
    fin=fopen("infasuratoarea.in" ,"r");
    fout=fopen("infasuratoarea.out" ,"w");
    fscanf(fin, "%d" ,&n);
    for(i=0;i<n;i++) {
        fscanf(fin, "%lf%lf" ,&v[i].x ,&v[i].y);

    }
    sort(v, v+n, cmp);
    sts[0].x=stt[0].x=v[0].x;
    sts[0].y=stt[0].y=v[0].y;
    sts[1].x=stt[1].x=v[1].x;
    sts[1].y=stt[1].y=v[1].y;
    i=l=2;
    for(k=2;k<n;k++) {
        drp(v[k].x, v[k].y);
    }
    fprintf(fout, "%d\n" ,i+l);
    for (k=0;k<l;k++) {
        fprintf(fout, "%.6lf %.6lf\n" ,sts[k].x, sts[k].y);
    }
    fprintf(fout, "%.6lf %.6lf\n" ,v[n-1].x ,v[n-1].y);
    for (k=i-1;k>0;k--) {
        fprintf(fout, "%.6lf %.6lf\n" ,stt[k].x, stt[k].y);
    }
    return 0;
}