Cod sursa(job #1758656)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 17 septembrie 2016 16:47:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stack>
using namespace std;

#define MAX_NR_PUNCTE 120000
#define MAX_COORD 1000000000.0
typedef struct {
    double x;
    double y;
} coordonata;

long nr_puncte;
coordonata punct[MAX_NR_PUNCTE];
coordonata first;
long i_first;

void swap_punct(coordonata *p1, coordonata *p2) {
    coordonata aux;
    aux = *p1;
    *p1 = *p2;
    *p2 = aux;
}

void citire() {
    long i;
    int err;
    first.x = MAX_COORD;
    first.y = MAX_COORD;
    FILE *in = fopen("infasuratoare.in", "rt");
    err = fscanf(in, "%ld\n", &nr_puncte);
    for (i = 0; i < nr_puncte; i++) {
        err = fscanf(in, "%lf %lf\n", &punct[i].x, &punct[i].y);
        if (punct[i].x < first.x || (punct[i].x == first.x && punct[i].y < first.y)) {
            first.x = punct[i].x;
            first.y = punct[i].y;
            i_first = i;
        }
    }
    fclose(in);
    swap_punct(&punct[0], &punct[i_first]);
}

bool comp_first(coordonata c1, coordonata c2) {
    double m1 = (c1.y - first.y) / (c1.x - first.x);
    double m2 = (c2.y - first.y) / (c2.x - first.x);
    return m1 > m2;
}

void verificare() {
    printf("-----VERIFICARE-----\n");
    for (long i = 0; i < nr_puncte; i++) {
        printf("x %lf y %lf\n", punct[i].x, punct[i].y);
    }
    printf("first: x %lf y %lf\n", first.x, first.y);
}

double unghi_polar(coordonata p1, coordonata p2, coordonata p3) {
    /*if ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) < 0) {
        return true;
    }
    return false;*/
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

int main()
{
    long i;

    citire();
    sort(punct + 1, punct + nr_puncte, comp_first);

    stack<coordonata> final;
    final.push(punct[0]);
    final.push(punct[1]);
    coordonata aux1, aux2;
    for (i = 2; i < nr_puncte; i++) {
        while (true) {
            aux1 = final.top();
            final.pop();
            aux2 = final.top();
            if (unghi_polar(aux2, aux1, punct[i]) < 0) {
                final.push(aux1);
                final.push(punct[i]);
                break;
            }
        }
    }

    FILE *out = fopen("infasuratoare.out", "wt");
    fprintf(out, "%ud\n", final.size());
    while (!final.empty()) {
        first = final.top();
        final.pop();
        fprintf(out, "%lf %lf\n", first.x, first.y);
    }
    fclose(out);
    //verificare();

    return 0;
}