Cod sursa(job #416022)

Utilizator recviemAlexandru Pana recviem Data 12 martie 2010 01:29:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#define NMAX 100000

typedef struct{
    double x, y;
}point;

point p[NMAX], rez[NMAX];
int n, rC;

void readPoints(){
    FILE* f = fopen("infasuratoare.in","r");
    fscanf(f, "%d", &n);
    int min = 0;
    for (int i = 0; i < n; i++){
        fscanf(f,"%lf %lf", &p[i].x, &p[i].y);
        if (p[i].y < p[min].y)
            min = i;
    }
    point aux = p[min];
    p[min] = p[0];
    p[0] = aux;
}

void writePoints(){
    freopen("infasuratoare.out", "w", stdout);
    printf("%d\n", rC);
    for (int i = 1; i<=rC; i++)
        printf("%lf %lf\n", rez[i].x, rez[i].y);
}

int operator<(point a, point b){
    return atan2(a.y, a.x) < atan2(b.y, b.x);
    /*
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
    */
}

int ccw(point p1, point p2, point p3){
    return (int)((p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x));
}

void grahamScan(){
    // sort by X and then by Y
    std::sort(p+1, p+n);
    p[n] = p[0];
    rC = 0;
    rez[++rC] = p[0];
    rez[++rC] = p[1];
    for (int i = 2; i<n; i++){
        while (ccw(rez[rC-1], rez[rC], p[i]) < 0 && rC > 2)
            rC--;
        rez[++rC] = p[i];
    }
}

int main(){
    readPoints();
    grahamScan();
    for (int i=0; i<n; i++)
        printf("%lf %lf\n", p[i].x, p[i].y);
    writePoints();
    //getchar();
    return 0;
}