Cod sursa(job #2399559)

Utilizator CojocariuAlexandruCojocariu Alexandru CojocariuAlexandru Data 7 aprilie 2019 18:45:09
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>
#include <cmath>
#define NMAX 120050
#define INF 999999999

using namespace std;

FILE *fin = fopen("infasuratoare.in", "r");
ofstream fout2("infasuratoare.out");

struct points{
    double x, y;
};
points P[NMAX];

struct angles{
    double difx, dify;
    int index;
};
angles A[NMAX];
double criteriu(angles a, angles b){
    if(a.dify*b.difx > a.difx*b.dify)
        return 1;
    return 0;
}
double parteGresita(double,double,double,double,double,double);

int n, i, ct, elemStiva, stiva[NMAX], pivot, ymax;
double xmin;

int main(){
    fscanf(fin, "%d", &n);
    xmin = INF, ymax=-1;
    for(i=1; i<=n; ++i){
        fscanf(fin, "%lf%lf", &P[i].x, &P[i].y);
        if(xmin > P[i].x || (xmin == P[i].x && ymax < P[i].y)){
            xmin = P[i].x;
            ymax = P[i].y;
            pivot = i;
            }
        }
    for(i=1; i<=n; ++i){
        if(i==pivot)
            continue;
            else{
                A[ct].difx = P[i].x - P[pivot].x;
                A[ct].dify = P[i].y - P[pivot].y;
                A[ct].index = i;
                ++ct;
                }
        }
    sort(A, A+ct, criteriu);
    elemStiva = 0;
    for(i=0; i<ct; ++i){
        stiva[elemStiva] = A[i].index;
        ++elemStiva;
        while(elemStiva >= 3
               && parteGresita(P[stiva[elemStiva-1]].x, P[stiva[elemStiva-1]].y, P[stiva[elemStiva-2]].x, P[stiva[elemStiva-2]].y, P[stiva[elemStiva-3]].x, P[stiva[elemStiva-3]].y) == 1){
            stiva[elemStiva-2] = stiva[elemStiva-1];
            elemStiva--;
            }
        }
    if(parteGresita(P[pivot].x, P[pivot].y, P[stiva[elemStiva-1]].x, P[stiva[elemStiva-1]].y, P[stiva[elemStiva-2]].x, P[stiva[elemStiva-2]].y)== 1){
        elemStiva--;
        }
    fout2 << setprecision(13) << fixed << elemStiva+1 << '\n';
    fout2 << P[pivot].x << ' ' << P[pivot].y << '\n';
    for(i=0; i<elemStiva; ++i)
        fout2 << setprecision(13) << fixed << P[stiva[i]].x << ' ' << P[stiva[i]].y  << '\n';
    fout2 << '\n';
    fclose(fin);
    fout2.close();
    return 0;
}

double parteGresita(double x1,double y1,double x,double y,double x2,double y2){
    double val;
    val = x*(y2-y1) + y*(x1-x2) + y1*x2 - x1*y2;
    if(val <= 0)
        return 1;
    return 0;
}