Cod sursa(job #1758658)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 17 septembrie 2016 16:57:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 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;
    first.x = MAX_COORD;
    first.y = MAX_COORD;
    FILE *in = fopen("infasuratoare.in", "rt");
    fscanf(in, "%ld\n", &nr_puncte);
    for (i = 0; i < nr_puncte; i++) {
        fscanf(in, "%lf %lf\n", &punct[i].x, &punct[i].y);
        if (punct[i].x < first.x) {
            first = punct[i];
            i_first = i;
        } else if (punct[i].x == first.x && punct[i].y < first.y) {

        }
    }
    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) {
    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);

    coordonata final[MAX_NR_PUNCTE];
    long final_size = 2;
    final[0] = punct[0];
    final[1] = punct[1];

    for (i = 2; i < nr_puncte; i++) {
        while (true) {
            if (unghi_polar(final[final_size - 2], final[final_size - 1], punct[i]) < 0) {
                final[final_size++] = punct[i];
                break;
            } else {
                final_size--;
            }
        }
    }

    FILE *out = fopen("infasuratoare.out", "wt");
    fprintf(out, "%u\n", final_size);
    for (i = 0; i < final_size; i++) {
        fprintf(out, "%lf %lf\n", final[i].x, final[i].y);
    }
    fclose(out);

    //verificare();

    return 0;
}